程序代写代做代考 Transport Layer

Transport Layer

All material copyright 1996-2012
J.F Kurose and K.W. Ross, All Rights Reserved

George Parisis
School of Engineering and Informatics

University of Sussex

Transport Layer 3-2

Outline
v  transport-layer services
v  multiplexing and demultiplexing
v  connectionless transport: UDP
v  principles of reliable data transfer
v  connection-oriented transport: TCP

§  segment structure
§  reliable data transfer
§  flow control
§  connection management

v  principles of congestion control
v  TCP congestion control

Transport Layer 3-3

Pipelined protocols
pipelining: sender allows multiple, “in-flight”,

yet-to-be-acknowledged pkts
§  range of sequence numbers must be increased
§ buffering at sender and/or receiver

v  two generic forms of pipelined protocols: go-
Back-N, selective repeat

Transport Layer 3-4

Pipelining: increased utilization

first packet bit transmitted, t = 0

sender receiver

RTT

last bit transmitted, t = L / R

first packet bit arrives
last packet bit arrives, send ACK

ACK arrives, send next
packet, t = RTT + L / R

last bit of 2nd packet arrives, send ACK
last bit of 3rd packet arrives, send ACK

3-packet pipelining increases
utilization by a factor of 3!

U
sender =

.0024
30.008

= 0.00081
3L / R

RTT + L / R
=

Transport Layer 3-5

Pipelined protocols: overview
Go-back-N:
v  sender can have up

to N unacked packets
in pipeline

v  receiver only sends
cumulative ack
§ doesn’t ack packet if

there’s a gap
v  sender has timer for

oldest unacked
packet
§ when timer expires,

retransmit all unacked
packets

Selective Repeat:
v  sender can have up to

N unacked packets in
pipeline

v  rcvr sends individual
ack for each packet

v  sender maintains timer

for each unacked
packet
§ when timer expires,

retransmit only that
unacked packet

Transport Layer 3-6

Go-Back-N: sender
v  k-bit seq # in pkt header
v  “window” of up to N, consecutive unack’ed pkts allowed

v  ACK(n): ACKs all pkts up to, including seq # n –
“cumulative ACK”
§ may receive duplicate ACKs (see receiver)

v  timer for oldest in-flight pkt
v  timeout(n): retransmit packet n and all higher seq # pkts

in window

Transport Layer 3-7

GBN: sender extended FSM

Wait start_timer udt_send(sndpkt[base])
udt_send(sndpkt[base+1])

udt_send(sndpkt[nextseqnum-1]
)

timeout

rdt_send(data)
if (nextseqnum < base+N) { sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum]) if (base == nextseqnum) start_timer nextseqnum++ } else refuse_data(data) base = getacknum(rcvpkt)+1 If (base == nextseqnum) stop_timer else start_timer rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) base=1 nextseqnum=1 rdt_rcv(rcvpkt) && corrupt(rcvpkt) Λ Λ Transport Layer 3-8 ACK-only: always send ACK for correctly-received pkt with highest in-order seq # § may generate duplicate ACKs § need only remember expectedseqnum v  out-of-order pkt: § discard (don’t buffer): no receiver buffering! §  re-ACK pkt with highest in-order seq # Wait udt_send(sndpkt) default rdt_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) Λ GBN: receiver extended FSM Transport Layer 3-9 GBN in action send pkt0 send pkt1 send pkt2 send pkt3 (wait) sender receiver receive pkt0, send ack0 receive pkt1, send ack1 receive pkt3, discard, (re)send ack1 rcv ack0, send pkt4 rcv ack1, send pkt5 pkt 2 timeout send pkt2 send pkt3 send pkt4 send pkt5 X loss receive pkt4, discard, (re)send ack1 receive pkt5, discard, (re)send ack1 rcv pkt2, deliver, send ack2 rcv pkt3, deliver, send ack3 rcv pkt4, deliver, send ack4 rcv pkt5, deliver, send ack5 ignore duplicate ACK 0 1 2 3 4 5 6 7 8 sender window (N=4) 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 Transport Layer 3-10 Selective repeat v  receiver individually acknowledges all correctly received pkts § buffers pkts, as needed, for eventual in-order delivery to upper layer v  sender only resends pkts for which ACK not received § sender timer for each unACKed pkt v  sender window § N consecutive seq #’s §  limits number of sent, unACKed pkts Transport Layer 3-11 Selective repeat: sender, receiver windows Transport Layer 3-12 Selective repeat data from above: v  if next available seq # in window, send pkt timeout(n): v  resend pkt n, restart timer ACK(n) in [sendbase,sendbase+N]: v  mark pkt n as received v  if n smallest unACKed pkt, advance window base to next unACKed seq # sender pkt n in [rcvbase, rcvbase+N-1] v  send ACK(n) v  out-of-order: buffer v  in-order: deliver (also deliver buffered, in-order pkts), advance window to next not- yet-received pkt pkt n in [rcvbase-N,rcvbase-1] v  ACK(n) otherwise: v  ignore receiver Transport Layer 3-13 Selective repeat in action send pkt0 send pkt1 send pkt2 send pkt3 (wait) sender receiver receive pkt0, send ack0 receive pkt1, send ack1 receive pkt3, buffer, send ack3 rcv ack0, send pkt4 rcv ack1, send pkt5 pkt 2 timeout send pkt2 X loss receive pkt4, buffer, send ack4 receive pkt5, buffer, send ack5 rcv pkt2; deliver pkt2, pkt3, pkt4, pkt5; send ack2 record ack3 arrived 0 1 2 3 4 5 6 7 8 sender window (N=4) 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 record ack4 arrived record ack5 arrived Q: what happens when ack2 arrives? Transport Layer 3-14 Selective repeat: dilemma example: v  seq #’s: 0, 1, 2, 3 v  window size=3 receiver window (after receipt) sender window (after receipt) 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 pkt0 pkt1 pkt2 0 1 2 3 0 1 2 pkt0 timeout retransmit pkt0 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 X X X will accept packet with seq number 0 (b) oops! 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 pkt0 pkt1 pkt2 0 1 2 3 0 1 2 pkt0 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 X will accept packet with seq number 0 0 1 2 3 0 1 2 pkt3 (a) no problem receiver can’t see sender side. receiver behavior identical in both cases! something’s (very) wrong! v  receiver sees no difference in two scenarios! v  duplicate data accepted as new in (b) Q: what relationship between seq # size and window size to avoid problem in (b)? Reordering v  Old copies of a packet with a sequence or acknowledgment number of x can appear §  neither the sender’s nor the receiver’s window contains x v  Channel can be thought of as essentially buffering packets and spontaneously emitting these packets at any point in the future v  Care must be taken to guard against duplicate sequence numbers. v  A sequence number must not be reused until the sender is “sure” that any previously sent packets with sequence number x are no longer in the network. v  This is done by assuming that a packet cannot “live” in the network for longer than some fixed maximum amount of time. Transport Layer 3-15 Transport Layer 3-16 Summary v  principles behind transport layer services: § reliable data transfer § GBN § Selective repeat