02 Chapter2 Application Layer.pptx

第1页：第3章：运输层

第3章：运输层

• understand principles behind transport layer services:
  • multiplexing/demultiplexing
  • 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

第2页：第3章路线图

第3章路线图

• 3.1 Transport-layer services
• 3.2 Multiplexing anddemultiplexing
• 3.3 Connectionless transport: UDP
• 3.4 Principles ofreliable data transfer
• 3.5 Connection-oriented transport: TCP
  • segment structure
  • reliable data transfer
  • flow control
  • connection management
• 3.6 Principles ofcongestion control
• 3.7 TCP congestion control

第3页：运输服务和协议

运输服务和协议

• provide logical communication between app processes running on different hosts
• transport protocols run inend systems
  • send side: breaks appmessages intosegments,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 UDPapplication transport networkdata link physical application transport networkdata link physical logical end-end transport

第4页：运输 vs. 网络层

运输 vs. 网络层

• 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 = lettersin envelopes
• hosts = houses
• transport protocol =Ann and Bill
• network-layer protocol= postal service

第5页：Internet transport-layer protocols

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 networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata link physical application transport networkdata link physical logical end-end transport

第6页：第3章路线图

第3章路线图

• 3.1 Transport-layer services
• 3.2 Multiplexing anddemultiplexing
• 3.3 Connectionless transport: UDP
• 3.4 Principles ofreliable data transfer
• 3.5 Connection-oriented transport: TCP
  • segment structure
  • reliable data transfer
  • flow control
  • connection management
• 3.6 Principles ofcongestion control
• 3.7 TCP congestion control

第7页：Multiplexing/demultiplexing application

Multiplexing/demultiplexing application

Multiplexing/demultiplexing application transport networklink physical P1 application transport networklink physical application transport networklink physical P2P3P4P1 host 1 host 2 host 3= process= socket delivering received segmentsto correct socket Demultiplexing at rcv host:gathering data from multiple sockets, enveloping data withheader (later used fordemultiplexing)Multiplexing at send host:

第8页：如何多路分解 works

如何多路分解 works

• host receives IP datagrams
  • each datagram has source IP address, destination IPaddress
  • each datagram carries 1 transport-layer segment
  • each segment has source,destination port number
• host uses IP addresses & portnumbers to direct segment toappropriate socket source port #dest port #32 bitsapplicationdata(message)other header fields TCP/UDP segment format

第9页：无连接多路分解

无连接多路分解

• Create sockets with portnumbers:Datagram Socket my Socket 1 = new Datagram Socket(12534);Datagram Socket my Socket 2 = new Datagram Socket(12535);
• UDP socket identified bytwo-tuple:(dest IP address, dest port number)
• When host receives UDPsegment:
  • checks destination portnumber in segment
  • directs UDP segment tosocket with that portnumber
• IP datagrams withdifferent source IPaddresses and/or sourceport numbers directedto same socket

第10页：Connectionless demux (cont)Datagram

Connectionless demux (cont)Datagram

Connectionless demux (cont)Datagram Socket server Socket = new Datagram Socket(6428);Client IP:BP2 client IP: AP1P1P3 server IP: CSP: 6428DP: 9157SP: 9157DP: 6428SP: 6428DP: 5775SP: 5775DP: 6428SP provides “return address”

第11页：Connection-oriented demux

Connection-oriented demux

• TCP socket identifiedby 4-tuple:
  • source IP address
  • source port number
  • dest IP address
  • dest port number
• recv host uses all fourvalues to direct segment to appropriate socket
• Server host may supportmany simultaneous TCPsockets:
  • each socket identified byits own 4-tuple
• Web servers havedifferent sockets foreach connecting client
  • non-persistent HTTP willhave different socket foreach request

第12页：Connection-oriented

Connection-oriented

Connection-oriented demux(cont)Client IP:BP1 client IP: AP1P2P4 server IP: CSP: 9157DP: 80SP: 9157DP: 80P5P6P3D-IP:CS-IP: AD-IP:CS-IP: BSP: 5775DP: 80D-IP:CS-IP: B

第13页：Connection-oriented

Connection-oriented

Connection-oriented demux:Threaded Web Server Client IP:BP1 client IP: AP1P2 server IP: CSP: 9157DP: 80SP: 9157DP: 80P4P3D-IP:CS-IP: AD-IP:CS-IP: BSP: 5775DP: 80D-IP:CS-IP: B

第14页：第3章路线图

第3章路线图

• 3.1 Transport-layer services
• 3.2 Multiplexing anddemultiplexing
• 3.3 Connectionless transport: UDP
• 3.4 Principles ofreliable data transfer
• 3.5 Connection-oriented transport: TCP
  • segment structure
  • reliable data transfer
  • flow control
  • connection management
• 3.6 Principles ofcongestion control
• 3.7 TCP congestion control

第15页：UDP: User Datagram Protocol[RFC 768]

UDP: User Datagram Protocol[RFC 768]

• “no frills,” “bare bones”Internet transport protocol
• “best effort” service, UDPsegments may be:
  • lost
  • delivered out of orderto app
• connectionless:
  • no handshaking between UDP sender, receiver
  • each UDP segment handled independentlyof others Why is there a UDP?
• no connection establishment (which canadd delay)
• simple: no connection stateat sender, receiver
• small segment header
• no congestion control: UDPcan blast away as fast asdesired

第16页：UDP补充

UDP补充

• often used for streaming multimedia apps
  • loss tolerant
  • rate sensitive
• other UDP uses
  • DNS
  • SNMP
• reliable transfer over UDP:add reliability atapplication layer
  • application-specific error recovery!source port #dest port #32 bits Applicationdata(message)UDP segment format length checksum Length, inbytes of UDPsegment,includingheader

第17页：UDP 检验和发送方

UDP 检验和发送方

• treat segment contentsas sequence of 16-bitintegers
• checksum: addition (1’scomplement sum) ofsegment contents
• sender puts checksum value into UDP checksum field Receiver:
• compute checksum ofreceived segment
• check if computed checksum equals checksum field value:
  • NO-error detected
  • YES-no error detected. But maybe errors nonetheless?More later…. Goal:detect “errors” (e.g., flipped bits) in transmitted segment

第18页：因特网检验和示例

因特网检验和示例

• Note
  • When adding numbers, a carryout from themost significant bit needs to be added to theresult
• Example: add two 16-bit integers 11 1 1 0 0 1 1 0 0 1 1 0 0 1 1 011 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 111 0 1 1 1 0 1 1 1 0 1 1 1 1 0 010 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 wraparoundsum checksum

第19页：第3章路线图

第3章路线图

• 3.1 Transport-layer services
• 3.2 Multiplexing anddemultiplexing
• 3.3 Connectionless transport: UDP
• 3.4 Principles ofreliable data transfer
• 3.5 Connection-oriented transport: TCP
  • segment structure
  • reliable data transfer
  • flow control
  • connection management
• 3.6 Principles ofcongestion control
• 3.7 TCP congestion control

第20页：可靠数据传输原理

可靠数据传输原理

• 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)

第21页：可靠数据传输原理

可靠数据传输原理

• 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)

第22页：可靠数据传输原理

可靠数据传输原理

• 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)

第23页：可靠数据传输获取 startedse

可靠数据传输获取 startedse

Reliable data transfer: getting startedsendsidereceivesiderdt_send():called from above,(e.g., by app.). Passed data todeliver to receiver upper layerudt_send():called by rdt,to transfer packet overunreliable channel to receiverrdt_rcv():called when packet arrives on rcv-side of channel deliver_data():called byrdtto deliver data to upper

第24页：可靠数据传输入门 We’ll

可靠数据传输入门 We’ll

• incrementally develop sender, receiver sides ofreliable 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 1 state 2 event causing state transition actions taken on state transition state:when in this“state” next state uniquely determinedby next event event actions

第25页：Rdt 1.0:reliable transfer over reliable

Rdt 1.0:reliable transfer over reliable

• underlying channel perfectly reliable
  • no bit errors
  • no loss of packets
• separate FSMs for sender, receiver:
  • sender sends data into underlying channel
  • receiver read data from underlying channel Wait forcall from above packet = make_pkt(data)udt_send(packet)rdt_send(data)extract (packet,data)deliver_data(data)Wait forcall frombelowrdt_rcv(packet)sender receiver

第26页：Rdt 2.0:channel with bit errors

Rdt 2.0:channel with bit errors

• underlying channel may flip bits in packet
  • checksum to detect bit errors
• thequestion: how to recover from errors:
  • acknowledgements (ACKs):receiver explicitly tells senderthat pkt received OK
  • negative acknowledgements (NAKs):receiver explicitlytells sender that pkt had errors
  • sender retransmits pkt on receipt of NAK
• new mechanisms inrdt 2.0(beyondrdt 1.0):
  • error detection
  • receiver feedback: control msgs (ACK, NAK) rcvr->sender

第27页：rdt 2.0: FSM specification Wait forcall

rdt 2.0: FSM specification Wait forcall

rdt 2.0: FSM specification Wait forcall fromabovesnkpkt = make_pkt(data, checksum)udt_send(sndpkt)extract(rcvpkt,data)deliver_data(data)udt_send(ACK)rdt_rcv(rcvpkt) &&notcorrupt(rcvpkt)rdt_rcv(rcvpkt) && is ACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt) &&is NAK(rcvpkt)udt_send(NAK)rdt_rcv(rcvpkt) &&corrupt(rcvpkt)Wait for ACK or NAKWait forcall from below sender receiverrdt_send(data)

第28页：rdt 2.0：操作与无差错

rdt 2.0：操作与无差错

rdt 2.0: operation with no errors Wait forcall fromabovesnkpkt = make_pkt(data, checksum)udt_send(sndpkt)extract(rcvpkt,data)deliver_data(data)udt_send(ACK)rdt_rcv(rcvpkt) &&notcorrupt(rcvpkt)rdt_rcv(rcvpkt) && is ACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt) &&is NAK(rcvpkt)udt_send(NAK)rdt_rcv(rcvpkt) &&corrupt(rcvpkt)Wait for ACK or NAKWait forcall frombelowrdt_send(data)

第29页：rdt 2.0: error scenario Wait forcall

rdt 2.0: error scenario Wait forcall

rdt 2.0: error scenario Wait forcall fromabovesnkpkt = make_pkt(data, checksum)udt_send(sndpkt)extract(rcvpkt,data)deliver_data(data)udt_send(ACK)rdt_rcv(rcvpkt) &&notcorrupt(rcvpkt)rdt_rcv(rcvpkt) && is ACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt) &&is NAK(rcvpkt)udt_send(NAK)rdt_rcv(rcvpkt) &&corrupt(rcvpkt)Wait for ACK or NAKWait forcall frombelowrdt_send(data)

第30页：rdt 2.0 has fatal flaw!

rdt 2.0 has fatal flaw!

• sender doesn’t know whathappened at receiver!
• can’t just retransmit:possible duplicate Handling duplicates:
• sender retransmits currentpkt if ACK/NAK garbled
• sender addssequencenumberto each pkt
• receiver discards (doesn’tdeliver up) duplicate pkt Sender sends one packet,then waits for receiver responsestop and wait

第31页：rdt 2.1: sender, handles garbled

rdt 2.1: sender, handles garbled

rdt 2.1: sender, handles garbled ACK/NAKs Wait forcall 0 fromabovesndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)rdt_send(data)Wait for ACK or NAK 0 udt_send(sndpkt)rdt_rcv(rcvpkt) &&( corrupt(rcvpkt) ||is NAK(rcvpkt) )sndpkt = make_pkt(1, data, checksum)udt_send(sndpkt)rdt_send(data)rdt_rcv(rcvpkt)&& notcorrupt(rcvpkt)&& is ACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt) &&( corrupt(rcvpkt) ||is NAK(rcvpkt) )rdt_rcv(rcvpkt)&& notcorrupt(rcvpkt)&& is ACK(rcvpkt)Wait forcall 1 fromabove Wait for ACK or NAK 1

第32页：rdt 2.1: receiver, handles garbled

rdt 2.1: receiver, handles garbled

rdt 2.1: receiver, handles garbled ACK/NAKs Wait for 0 frombelowsndpkt = make_pkt(NAK, chksum)udt_send(sndpkt)rdt_rcv(rcvpkt) &&not corrupt(rcvpkt) &&has_seq 0(rcvpkt)rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)&& has_seq 1(rcvpkt)extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)Wait for 1 frombelowrdt_rcv(rcvpkt) && notcorrupt(rcvpkt)&& has_seq 0(rcvpkt)extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)rdt_rcv(rcvpkt) && (corrupt(rcvpkt)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)rdt_rcv(rcvpkt) &&not corrupt(rcvpkt) &&has_seq 1(rcvpkt)rdt_rcv(rcvpkt) && (corrupt(rcvpkt)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)sndpkt = make_pkt(NAK, chksum)udt_send(sndpkt)

第33页：rdt 2.1：讨论发送方

rdt 2.1：讨论发送方

• seq # added to pkt
• two seq. #’s (0,1) willsuffice. Why?
• must check if received ACK/NAK corrupted
• twice as many states
  • state must “remember”whether “current” pkthas 0 or 1 seq. #Receiver:
• must check if received packet is duplicate
  • state indicates whether 0 or 1 is expected pktseq #
• note: receiver cannotknow if its last ACK/NAK received OKat sender

第34页：rdt 2.2: NAK-free protocol

rdt 2.2: NAK-free protocol

• same functionality as rdt 2.1, using ACKs only
• instead of NAK, receiver sends ACK for last pktreceived OK
  • receiver mustexplicitlyinclude seq # of pkt being ACKed
• duplicate ACK at sender results in same action as NAK:retransmit current pkt

第35页：rdt 2.2: sender, receiver fragments Wait

rdt 2.2: sender, receiver fragments Wait

rdt 2.2: sender, receiver fragments Wait forcall 0 fromabovesndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)rdt_send(data)udt_send(sndpkt)rdt_rcv(rcvpkt) &&( corrupt(rcvpkt) ||is ACK(rcvpkt,1))rdt_rcv(rcvpkt)&& notcorrupt(rcvpkt)&&is ACK(rcvpkt,0)Wait for ACK0 sender FSMfragment Wait for 0 frombelowrdt_rcv(rcvpkt) && notcorrupt(rcvpkt)&& has_seq 1(rcvpkt)extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK1, chksum)udt_send(sndpkt)rdt_rcv(rcvpkt) &&(corrupt(rcvpkt) ||has_seq 1(rcvpkt))udt_send(sndpkt)receiver FSMfragment

第36页：rdt 3.0：信道与差错

rdt 3.0：信道与差错

• checksum, seq. #, ACKs,retransmissions will beof help, but not enough Approach:sender waits“reasonable” amount oftime for ACK
• retransmits if no ACKreceived in this time
• if pkt (or ACK) just delayed(not lost):
  • retransmission will beduplicate, but use of seq.#’s already handles this
  • receiver must specify seq# of pkt being ACKed
• requires countdown timer

第37页：rdt 3.0 sender

rdt 3.0 sender

rdt 3.0 sendersndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)start_timerrdt_send(data)Waitfor ACK0 rdt_rcv(rcvpkt) &&( corrupt(rcvpkt) ||is ACK(rcvpkt,1) )Wait forcall 1 fromabovesndpkt = make_pkt(1, data, checksum)udt_send(sndpkt)start_timerrdt_send(data)rdt_rcv(rcvpkt)&& notcorrupt(rcvpkt)&& is ACK(rcvpkt,0)rdt_rcv(rcvpkt) &&( corrupt(rcvpkt) ||is ACK(rcvpkt,0) )rdt_rcv(rcvpkt)&& notcorrupt(rcvpkt)&& is ACK(rcvpkt,1)stop_timerstop_timerudt_send(sndpkt)start_timer timeoutudt_send(sndpkt)start_timer timeoutrdt_rcv(rcvpkt)Wait forcall 0 fromabove Waitfor ACK1 rdt_rcv(rcvpkt)

第38页：rdt 3.0 action

rdt 3.0 action

rdt 3.0 in action

第39页：rdt 3.0 action

rdt 3.0 action

rdt 3.0 in action

第40页：Performance rdt 3.0

Performance rdt 3.0

• rdt 3.0 works, but performance stinks
• example: 1 Gbps link, 15 ms e-e prop. delay, 1KB packet:Ttransmit=8 kb/pkt 10**9 b/sec= 8 microsec
  • Usender:utilization
  • fraction of time sender busy sending L (packet length in bits)R (transmission rate, bps)=
  • 1KB pkt every 30 msec-> 33 k B/sec thruput over 1 Gbps link
  • network protocol limits use of physical resources!

第41页：rdt 3.0: stop-and-wait

rdt 3.0: stop-and-wait

rdt 3.0: stop-and-wait operation first packet bit transmitted, t = 0 sender receiver RTTlast packet bit transmitted,t = L / Rfirst packet bit arriveslast packet bit arrives, send ACKACK arrives, send nextpacket,t = RTT + L / R

第42页：Pipelined protocols Pipelining:sender

Pipelined protocols Pipelining:sender

• range of sequence numbers must be increased
• buffering at sender and/or receiver
• Two generic forms of pipelined protocols:go-Back-N,selective repeat

第43页：流水线协议

流水线协议

Pipelining: increased utilization first packet bit transmitted, t = 0 sender receiver RTTlast bit transmitted, t = L / Rfirst packet bit arriveslast packet bit arrives, send ACKACK arrives, send nextpacket, t = RTT + L / Rlast bit of 2 ndpacket arrives, send ACKlast bit of 3 rdpacket arrives, send ACKIncrease utilizationby a factor of 3!

第44页：可靠数据传输原理（示意图）

可靠数据传输原理（示意图）

• k-bit seq # in pkt header
• “window” of up to N, consecutive unack’ed pkts allowed
• ACK(n): ACKs all pkts up to, including seq # n-“cumulative ACK”
  • may receive duplicate ACKs (see receiver)
• timer for each in-flight pkt
• timeout(n):retransmit pkt n and all higher seq # pkts in window

第45页：GBN: sender extended FSM

GBN: sender extended FSM

GBN: sender extended FSMWaitstart_timerudt_send(sndpkt[base])udt_send(sndpkt[base+1])…udt_send(sndpkt[nextseqnum-1])timeoutrdt_send(data)if (nextseqnum < base+N) {sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum)udt_send(sndpkt[nextseqnum])if (base == nextseqnum)start_timernextseqnum++}elserefuse_data(data)base = getacknum(rcvpkt)+1 If (base == nextseqnum)stop_timerelsestart_timerrdt_rcv(rcvpkt) &&notcorrupt(rcvpkt)base=1 nextseqnum=1 rdt_rcv(rcvpkt)&& corrupt(rcvpkt)

第46页：GBN: receiver extended FSM

GBN: receiver extended FSM

• may generate duplicate ACKs
• need only rememberexpectedseqnum
• out-of-order pkt:
  • discard (don’t buffer)->no receiver buffering!
  • Re-ACK pkt with highest in-order seq #Waitudt_send(sndpkt)defaultrdt_rcv(rcvpkt)&& notcurrupt(rcvpkt)&& hasseqnum(rcvpkt,expectedseqnum)extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(expectedseqnum, ACK,chksum)udt_send(sndpkt)expectedseqnum++expectedseqnum=1 sndpkt =make_pkt(expectedseqnum, ACK,chksum)

第47页：GBN inaction

GBN inaction

GBN inaction

第48页：选择重传

选择重传

• receiver individually acknowledges all correctly received pkts
  • buffers pkts, as needed, for eventual in-order deliveryto upper layer
• sender only resends pkts for which ACK notreceived
  • sender timer for each un ACKed pkt
• sender window
  • N consecutive seq #’s
  • again limits seq #s of sent, un ACKed pkts

第49页：选择重传发送方接收方窗口

选择重传发送方接收方窗口

Selective repeat: sender, receiver windows

第50页：选择重传

选择重传

• if next available seq # inwindow, send pkttimeout(n):
• resend pkt n, restart timer ACK(n)in[sendbase,sendbase+N]:
• mark pkt n as received
• if n smallest un ACKed pkt,advance window base tonext un ACKed seq #senderpkt n in[rcvbase, rcvbase+N-1]
• send ACK(n)
• out-of-order: buffer
• in-order: deliver (alsodeliver buffered, in-orderpkts), advance window tonext not-yet-received pktpkt n in[rcvbase-N,rcvbase-1]
• ACK(n)otherwise:
• ignore receiver

第51页：选择重传 动作

选择重传 动作

Selective repeat in action

第52页：Selective repeat:dilemma Example

Selective repeat:dilemma Example

• seq #’s: 0, 1, 2, 3
• window size=3
• receiver sees nodifference in twoscenarios!
• incorrectly passes duplicate data as newin (a)Q:what relationship between seq # sizeand window size?

第53页：第3章路线图

第3章路线图

• 3.1 Transport-layer services
• 3.2 Multiplexing anddemultiplexing
• 3.3 Connectionless transport: UDP
• 3.4 Principles ofreliable data transfer
• 3.5 Connection-oriented transport: TCP
  • segment structure
  • reliable data transfer
  • flow control
  • connection management
• 3.6 Principles ofcongestion control
• 3.7 TCP congestion control

第54页：TCP: Overview RFCs: 793, 1122, 1323

TCP: Overview RFCs: 793, 1122, 1323

• full duplex data:
  • bi-directional data flowin same connection
  • MSS: maximum segmentsize
• connection-oriented:
  • handshaking (exchangeof control msgs) init’ssender, receiver state before data exchange
• flow controlled:
  • sender will notoverwhelm receiver
• point-to-point:
  • one sender, one receiver
• reliable, in-orderbytesteam:
  • no “message bound aries”
• pipelined:
  • TCP congestion and flowcontrol set window size
• send & receive buffers

第55页：TCP 报文段结构源端口 #dest

TCP 报文段结构源端口 #dest

TCP segment structure source port #dest port #32 bitsapplicationdata(variable length)sequence number acknowledgement number Receive window Urg data pnterchecksum FSRPAUheadlennotused Options (variable length)URG: urgent data(generally not used)ACK: ACK #valid PSH: push data now(generally not used)RST, SYN, FIN:connection estab(setup, teardowncommands)# bytesrcvr willingto acceptcountingby bytesof data(not segments!)Internet checksum(as in UDP)

第56页：TCP seq. #’s and ACKs Seq

TCP seq. #’s and ACKs Seq

• byte stream“number” of firstbyte in segment’sdata ACKs:
• seq # of next byteexpected fromother side
• cumulative ACKQ:how receiver handlesout-of-order segments
• A: TCP spec doesn’tsay,-up toimplementor Host AHost BSeq=42, ACK=79, data = ‘C’Seq=79, ACK=43, data = ‘C’Seq=43, ACK=80 Usertypes‘C’host ACKsreceiptof echoed‘C’host ACKsreceipt of‘C’, echoesback ‘C’timesimple telnet scenario

第57页：TCP 往返时间和超时

TCP 往返时间和超时

• longer than RTT
  • but RTT varies
• too short: premature timeout
  • unnecessary retransmissions
• too long: slow reactionto segment loss Q:how to estimate RTT?
• Sample RTT:measured time fromsegment transmission until ACKreceipt
  • ignore retransmissions
• Sample RTTwill vary, wantestimated RTT “smoother”
  • average several recent measurements, not justcurrent Sample RTT

第58页：TCP 往返时间和超时

TCP 往返时间和超时

• Exponential weighted moving average
• influence of past sample decreases exponentially fast
• typical value: =0.125

第59页：Example RTT estimation

Example RTT estimation

Example RTT estimation:

第60页：TCP 往返时间和超时

TCP 往返时间和超时

• Estimted RTTplus “safety margin”
  • large variation in Estimated RTT->larger safety margin
• first estimate of how much Sample RTT deviates from Estimated RTT:Timeout Interval = Estimated RTT + 4*Dev RTTDev RTT = (1- )*Dev RTT + *|Sample RTT-Estimated RTT|(typically, = 0.25)Then set timeout interval:

第61页：第3章路线图

第3章路线图

• 3.1 Transport-layer services
• 3.2 Multiplexing anddemultiplexing
• 3.3 Connectionless transport: UDP
• 3.4 Principles ofreliable data transfer
• 3.5 Connection-oriented transport: TCP
  • segment structure
  • reliable data transfer
  • flow control
  • connection management
• 3.6 Principles ofcongestion control
• 3.7 TCP congestion control

第62页：TCP 可靠数据传输

TCP 可靠数据传输

• TCP creates rdtservice on top of IP’sunreliable service
• Pipelined segments
• Cumulative acks
• TCP uses single retransmission timer
• Retransmissions aretriggered by:
  • timeout events
  • duplicate acks
• Initially considersimplified TCP sender:
  • ignore duplicate acks
  • ignore flow control,congestion control

第63页：TCP sender events

TCP sender events

• Create segment withseq #
• seq # is byte-stream number of first databyte in segment
• start timer if notalready running (thinkof timer as for oldestunacked segment)
• expiration interval:Time Out Interval timeout:
• retransmit segmentthat caused timeout
• restart timer Ack rcvd:
• If acknowledges previously unackedsegments
  • update what is known tobe acked
  • start timer if there areoutstanding segments

第64页：TCP可靠数据传输（示意图）

TCP可靠数据传输（示意图）

• Send Base-1: lastcumulativelyack’ed byte Example:
• Send Base-1 = 71;y= 73, so the rcvrwants 73+ ;y > Send Base, sothat new data isacked

第65页：TCP: retransmission scenarios Host

TCP: retransmission scenarios Host

TCP: retransmission scenarios Host ASeq=100, 20 bytes data ACK=100 timepremature timeout Host BSeq=92, 8 bytes data ACK=120 Seq=92, 8 bytes data Seq=92 timeout ACK=120 Host ASeq=92, 8 bytes data ACK=100 losstimeoutlost ACK scenario Host BXSeq=92, 8 bytes data ACK=100 time Seq=92 timeout Send Base= 100 Send Base= 120 Send Base= 120 Sendbase= 100

第66页：TCP 重传场景补充

TCP 重传场景补充

TCP retransmission scenarios (more)Host ASeq=92, 8 bytes data ACK=100 losstimeout Cumulative ACK scenario Host BXSeq=100, 20 bytes data ACK=120 time Send Base= 120

第67页：TCP ACK generation[RFC 1122, RFC

TCP ACK generation[RFC 1122, RFC

TCP ACK generation[RFC 1122, RFC 2581]Event at Receiver Arrival of in-order segment withexpected seq #. All data up toexpected seq # already ACKed Arrival of in-order segment withexpected seq #. One other segment has ACK pending Arrival of out-of-order segmenthigher-than-expect seq. # . Gap detected Arrival of segment thatpartially or completely fills gap TCP Receiver action Delayed ACK. Wait up to 500 msfor next segment. If no next segment,send ACKImmediately send single cumulative ACK, ACKing both in-order segments Immediately sendduplicate ACK,indicating seq. # of next expected byte Immediate send ACK, provided thatsegment startsat lower end of gap

第68页：快速重传

快速重传

• Time-out period often relatively long:
  • long delay before resending lost packet
• Detect lost segmentsvia duplicate ACKs.
  • Sender often sendsmany segments back-to-back
  • If segment is lost,there will likely be manyduplicate ACKs.
• If sender receives 3ACKs for the samedata, it supposes thatsegment after ACKeddata was lost:
  • fast retransmit:resend segment before timer expires

第69页：TCP拥塞控制事件与动作

TCP拥塞控制事件与动作

event:ACK received, with ACK field value of yif (y > Send Base) {Send Base = yif (there are currently not-yet-acknowledged segments)start timer}else {increment count of dup ACKs received for yif (count of dup ACKs received for y = 3) {resend segment with sequence number y}Fast retransmit algorithm:a duplicate ACK foralready ACKed segmentfast retransmit

第70页：第3章路线图

第3章路线图

• 3.1 Transport-layer services
• 3.2 Multiplexing anddemultiplexing
• 3.3 Connectionless transport: UDP
• 3.4 Principles ofreliable data transfer
• 3.5 Connection-oriented transport: TCP
  • segment structure
  • reliable data transfer
  • flow control
  • connection management
• 3.6 Principles ofcongestion control
• 3.7 TCP congestion control

第71页：TCP 流量控制

TCP 流量控制

• receive side of TCPconnection has areceive buffer:
• speed-matching service: matching thesend rate to thereceiving app’s drainrate
• app process may beslow at reading from buffer sender won’t overflow receiver’s buffer bytransmitting too much,too fastflow control

第72页：TCP Flow control: it works(Suppose

TCP Flow control: it works(Suppose

• spare room in buffer= Rcv Window= Rcv Buffer-[Last Byte Rcvd-Last Byte Read]
• Rcvr advertises spareroom by including valueof Rcv Windowin segments
• Sender limits un ACKeddata to Rcv Window
  • guarantees receive buffer doesn’t overflow

第73页：第3章路线图

第3章路线图

• 3.1 Transport-layer services
• 3.2 Multiplexing anddemultiplexing
• 3.3 Connectionless transport: UDP
• 3.4 Principles ofreliable data transfer
• 3.5 Connection-oriented transport: TCP
  • segment structure
  • reliable data transfer
  • flow control
  • connection management
• 3.6 Principles ofcongestion control
• 3.7 TCP congestion control

第74页：TCP 连接管理

TCP 连接管理

• initialize TCP variables:
  • seq. #s
  • buffers, flow controlinfo (e.g. Rcv Window)
• client:connection initiator Socket client Socket = new Socket("hostname","portnumber");
• server:contacted by client Socket connection Socket =welcome Socket.accept();Three way handshake:Step 1:client host sends TCPSYN segment to server
  • specifies initial seq #
  • no data Step 2:server host receives SYN, replies with SYNACKsegment
  • server allocates buffers
  • specifies server initialseq. #Step 3:client receives SYNACK,replies with ACK segment,which may contain data

第75页：TCP Connection Management (cont.)

TCP Connection Management (cont.)

TCP Connection Management (cont.)Closing a connection:client closes socket:client Socket.close();Step 1:clientend systemsends TCP FIN control segment to server Step 2:server receives FIN, replies with ACK. Closes connection, sends FIN.client FINserver ACKACKFINclosecloseclosedtimed wait

第76页：TCP Connection Management (cont.)

TCP Connection Management (cont.)

• Enters “timed wait”-will respond with ACKto received FINs Step 4:server, receives ACK. Connection closed. Note:with small modification, can handle simultaneous FINs.client FINserver ACKACKFINclosingclosingclosedtimed waitclosed

第77页：TCP Connection Management (cont)TCP

TCP Connection Management (cont)TCP

TCP Connection Management (cont)TCP clientlife cycle TCP serverlife cycle

第78页：第3章路线图

第3章路线图

• 3.1 Transport-layer services
• 3.2 Multiplexing anddemultiplexing
• 3.3 Connectionless transport: UDP
• 3.4 Principles ofreliable data transfer
• 3.5 Connection-oriented transport: TCP
  • segment structure
  • reliable data transfer
  • flow control
  • connection management
• 3.6 Principles ofcongestion control
• 3.7 TCP congestion control

第79页：拥塞控制拥塞原理

拥塞控制拥塞原理

• informally: “too many sources sending too muchdata too fast fornetworkto handle”
• different from flow control!
• manifestations:
  • lost packets (buffer overflow at routers)
  • long delays (queueing in router buffers)
• a top-10 problem!

第80页：Causes/costs

Causes/costs

• two senders, tworeceivers
• one router,infinite buffers
• no retransmission
• large delayswhen congested
• maximum achievable throughputun limited shared output link buffers Host A
• in:original data Host B
• out

第81页：Causes/costs

Causes/costs

• one router,finite buffers
• sender retransmission of lost packet finite shared outputlink buffers Host A
• in: originaldata Host B
• out
• 'in: original data, plusretransmitted data

第82页：Causes/costs

Causes/costs

• always: (goodput)
• “perfect” retransmission only when loss:
• retransmission of delayed (not lost) packet makes larger(than perfect case) for same
• in
• out=
• in
• out>
• in
• out“costs” of congestion:
• more work (retrans) for given “goodput”
• unneeded retransmissions: link carries multiple copies of pkt R/2R/2
• in
• outb. R/2R/2
• in
• outa. R/2R/2
• in
• outc. R/4R/3

第83页：Causes/costs

Causes/costs

• four senders
• multihop paths
• timeout/retransmit
• in Q:what happens asand increase?
• infinite shared outputlink buffers Host A
• in: original data Host B
• out
• 'in: original data, plusretransmitted data

第84页：Causes/costs

Causes/costs

• when packet dropped, any “upstream transmission capacity used for that packet was wasted!Host AHost B
• out

第85页：Approaches towards congestion control

Approaches towards congestion control

• no explicit feedback fromnetwork
• congestion inferred fromend-system observed loss,delay
• approach taken by TCPNetwork-assisted congestion control:
• routers provide feedbackto end systems
  • single bit indicating congestion (SNA, DECbit, TCP/IP ECN, ATM)
  • explicit rate sender should send at Two broad approaches towards congestion control:

第86页：案例 ATM ABR 拥塞控制

案例 ATM ABR 拥塞控制

• “elastic service”
• if sender’s path“underloaded”:
  • sender should useavailable bandwidth
• if sender’s pathcongested:
  • sender throttled tominimum guaranteedrate RM (resource management)cells:
• sent by sender, interspersedwith data cells
• bits in RM cell set by switches(“network-assisted”)
  • NI bit:no increase in rate(mild congestion)
  • CI bit:congestion indication
• RM cells returned to sender byreceiver, with bits intact

第87页：案例 ATM ABR 拥塞控制

案例 ATM ABR 拥塞控制

• two-byte ER (explicit rate) field in RM cell
  • congested switch may lower ER value in cell
  • sender’ send rate thus maximum supportable rate on path
• EFCI bit in data cells: set to 1 in congested switch
  • if data cell preceding RM cell has EFCI set, sender sets CIbit in returned RM cell

第88页：第3章路线图

第3章路线图

• 3.1 Transport-layer services
• 3.2 Multiplexing anddemultiplexing
• 3.3 Connectionless transport: UDP
• 3.4 Principles ofreliable data transfer
• 3.5 Connection-oriented transport: TCP
  • segment structure
  • reliable data transfer
  • flow control
  • connection management
• 3.6 Principles ofcongestion control
• 3.7 TCP congestion control

第89页：TCP congestion control:additive increase

TCP congestion control:additive increase

• Approach:increase transmission rate (window size),probing for usable bandwidth, until loss occurs
  • additive increase:increase Cong Winby 1 MSSevery RTT until loss detected
  • multiplicative decrease:cut Cong Winin half afterlosstimecongestion window size Saw tooth behavior: probingfor bandwidth

第90页：TCP Congestion Control: details

TCP Congestion Control: details

• sender limits transmission:Last Byte Sent-Last Byte AckedCong Win
• Roughly,
• Cong Winis dynamic, functionof perceived network congestion How does sender perceive congestion?
• loss event = timeoutor 3 duplicate acks
• TCP sender reducesrate (Cong Win) afterloss event three mechanisms:
  • AIMD
  • slow start
  • conservative aftertimeout eventsrate =Cong Win RTTBytes/sec

第91页：TCP慢启动

TCP慢启动

• When connection begins, Cong Win= 1 MSS
  • Example: MSS = 500 bytes & RTT = 200 msec
  • initial rate = 20 kbps
• available bandwidth maybe >> MSS/RTT
  • desirable to quickly rampup to respectable rate
• When connection begins,increase rateexponentially fast until first loss event

第92页：TCP 慢启动补充

TCP 慢启动补充

• When connection begins, increase rateexponentially until first loss event:
  • double Cong Winevery RTT
  • done by incrementing Cong Winfor every ACKreceived
• Summary:initial rateis slow but ramps upexponentially fast Host Aone segment RTTHost Btimetwo segmentsfour segments

第93页：Refinement Q:When should thee

Refinement Q:When should thee

• Variable Threshold
• At loss event, Threshold isset to 1/2 of Cong Win justbefore loss event

第94页：Refinement: inferring loss

Refinement: inferring loss

• After 3 dup ACKs:
  • Cong Winis cut in half
  • window then growslinearly
• Butafter timeout event:
  • Cong Wininstead set to 1 MSS;
  • window then growsexponentially
  • to a threshold, thengrows linearly
• 3 dup ACKs indicates network capable ofdelivering some segments
• timeout indicates a“more alarming”congestion scenario Philosophy:

第95页：本章小结

本章小结

• When Cong Winis below Threshold, sender inslow-start phase, window grows exponentially.
• When Cong Winis above Threshold, sender is incongestion-avoidance phase, window grows linearly.
• When atriple duplicate ACKoccurs, Thresholdset to Cong Win/2 and Cong Winset to Threshold.
• Whentimeoutoccurs, Thresholdset to Cong Win/2 and Cong Winis set to 1 MSS.

第96页：TCP sender congestion control

TCP sender congestion control

TCP sender congestion control Commentary TCP Sender Action Event State Resulting in a doubling of Cong Win every RTTCong Win = Cong Win + MSS, If (Cong Win > Threshold)set state to“Congestion Avoidance”ACK receiptfor previouslyunackeddata Slow Start(SS)Additive increase, resultingin increase of Cong Win by 1 MSS every RTTCong Win = Cong Win+MSS *(MSS/Cong Win)ACK receiptfor previouslyunackeddata Congestion Avoidance(CA)Fast recovery,implementing multi plicativede crease. Cong Win will notdrop below 1 MSS. Threshold = Cong Win/2, Cong Win = Threshold, Set state to“Congestion Avoidance”Loss event detected bytriple duplicate ACKSS or CAEnter slow start Threshold = Cong Win/2, Cong Win = 1 MSS, Set state to“Slow Start”Timeout SS or CACong Win and Threshold notchanged Increment duplicate ACK countfor segment being acked Duplicate ACKSS or CA

第97页：TCP吞吐量

TCP吞吐量

• What’s the average throughout of TCP as afunction 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

第98页：TCP Futures: TCP over “long, fat

TCP Futures: TCP over “long, fat

• Example: 1500 byte segments, 100 ms RTT, want 10 Gbps throughput
• Requires window size W = 83,333 in-flight segments
• Throughput in terms of loss rate:
• ➜L = 2·10-10 Wow
• New versions of TCP for high-speed

第99页：Fairness goal:if K TCP sessions share

Fairness goal:if K TCP sessions share

Fairness goal:if K TCP sessions share samebottleneck link of bandwidth R, each should haveaverage rate of R/KTCP connection 1 bottleneck router capacity RTCPconnection 2TCP Fairness

第100页：TCP fair?Two comp

TCP fair?Two comp

• Additive increase gives slope of 1, as throughout increases
• multiplicative decrease decreases throughput proportionally RRequal bandwidth share Connection 1 throughput Connection 2 throughput congestion avoidance: additive increaseloss: decrease window by factor of 2 congestion avoidance: additive increaseloss: decrease window by factor of 2

第101页：公平性补充

公平性补充

• Multimedia apps oftendo not use TCP
  • do not want ratethrottled by congestion control
• Instead use UDP:
  • pump audio/video atconstant rate, tolerate packet loss
• Research area: TCPfriendly Fairness and parallel TCPconnections
• nothing prevents app fromopening parallel connections between 2 hosts.
• Web browsers do this
• Example: link of rate Rsupporting 9 connections;
  • new app asks for 1 TCP, getsrate R/10
  • new app asks for 11 TCPs,gets R/2 !

第102页：第3章小结

第3章小结

• principles behind transport layer services:
  • multiplexing,demultiplexing
  • reliable data transfer
  • flow control
  • congestion control
• instantiation andimple mentation in the Internet
  • UDP
  • TCPNext:
• leaving the network“edge” (application,transport layers)
• into the network“core”