计算机代考 RFC 768] - PowCoder代写

3rd Edition: Chapter 3

Computer Networking: A Top Down Approach

7th edition
April 2016
Transport Layer

The Powerpoint slides are from Kurose and Ross’s book’s website.
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 Internet transport layer protocols:
UDP: connectionless transport
TCP: connection-oriented reliable transport
TCP: congestion control

Transport Layer

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
3.6 principles of congestion control
3.7 TCP congestion control

Transport Layer

Transport layer services and protocols
provide logical end-to-end connection between app processes running on different hosts
Transport layer 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 layer protocol available to apps
Internet: TCP and UDP

application

logical end-end transport
Transport Layer

Transport vs. network layer
network layer: logical connection between hosts
transport layer: logical connection between processes
relies on, enhances, network layer services
12 kids in Ann’s house sending letters to 12 kids in Bill’s house:
hosts = houses
processes = kids
app messages = letters in envelopes
transport protocol = Ann and Bill who mux from (demux to) in-house siblings
network-layer protocol = postal service

household analogy:
Transport Layer

Internet transport layer protocols
reliable, in-order delivery (TCP)
congestion control
flow control
connection setup
unreliable, unordered delivery: UDP
extension of “best-effort” IP
no services for
delay guarantees
bandwidth guarantees

application

logical end-end transport

Transport Layer

Multiplexing/demultiplexing

use header info. to deliver
received segments to correct

demultiplexing at receiver:
handle data from multiple
sockets, add transport header (used for demultiplexing)

multiplexing at sender:

application

Transport Layer

How demultiplexing works
host receives IP datagrams
each datagram has source IP address, destination IP address
each datagram carries one transport-layer segment
each segment has source, destination port number
host uses IP addresses & port numbers to direct segment to appropriate socket
source port #
dest port #

application
other header fields
TCP/UDP segment format
Transport Layer

Connectionless demultiplexing
when host receives UDP segment:
checks destination port # in segment
directs UDP segment to socket with that port #
IP datagrams with same destination port #, but different source IP addresses and/or source port numbers will be directed to same socket at destination

Transport Layer

Connectionless demux: example
DatagramSocket serverSocket = new DatagramSocket

application

DatagramSocket mySocket1 = new DatagramSocket (5775);

DatagramSocket mySocket2 = new DatagramSocket

source port: 9157
dest port: 6428

source port: 6428
dest port: 9157

source port: ?
dest port: ?

Transport Layer

Connection-oriented demux
TCP socket identified by 4-tuple:
source IP address
source port number
dest IP address
dest port number
demux: receiver 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

Connection-oriented demux: example

application

source IP,port: A,9157
dest IP,port: B,80

source IP,port: B,80
dest IP,port: A,9157
IP address A
IP address C

source IP,port: C,5775
dest IP,port: B,80

source IP,port: C,9157
dest IP,port: B,80
three segments, all destined to server with IP address: B, dest port: 80, are demuxed to different sockets

IP address B

Transport Layer

Connection-oriented demux: example

application

source IP,port: A,9157
dest IP, port: B,80

source IP,port: B,80
dest IP,port: A,9157

source IP,port: C,5775
dest IP,port: B,80

source IP,port: C,9157
dest IP,port: B,80
threaded server

IP address A
IP address C
IP address B
Transport Layer

Transport Layer

UDP: User Datagram Protocol [RFC 768]
provide “best effort” service – UDP segments may be:
delivered out-of-order to app
connectionless:
no handshaking between UDP sender & receiver
each UDP segment is handled independently of others
UDP used in:
streaming multimedia apps (loss tolerant, rate sensitive)
reliable transfer over UDP:
add reliability at application layer
application-specific error recovery!
Transport Layer

UDP: segment header

source port #
dest port #

application
UDP segment format

length, in bytes of UDP segment, including header

no connection establishment (which can add delay)
simple: no connection state at sender & receiver
small header size

why is there a UDP?
Transport Layer

UDP checksum
treat segment contents, including header fields, as sequence of 16-bit integers
checksum: addition (one’s complement sum) of segment contents
sender puts checksum value into UDP checksum field

compute checksum of received segment
check if computed checksum equals checksum field value:
NO – error detected
YES – no error detected,
but maybe errors.
More later ….

Goal: detect “errors” (e.g., flipped bits) in transmitted segment

Transport Layer

Internet checksum: example
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

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

wraparound

Note: when adding numbers, a carryout from the most significant bit needs to be added to the result

Transport Layer

Kurose and Ross forgot to say anything about wrapping the carry and adding it to low order bit

Transport Layer

Principles of reliable data transfer
important in application, 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

characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)

Principles of reliable data transfer
important in application, transport, link layers
top-10 list of important networking topics!

Transport Layer

characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)

important in application, transport, link layers
top-10 list of important networking topics!

Principles of reliable data transfer
Transport Layer

Reliable data transfer: getting started

rdt_send(): called from above, (e.g., by app.). Pass data to
sending side rdt

udt_send(): called by rdt,
to transfer packet over
unreliable channel to receiver

rdt_rcv(): called when packet arrives on rcv-side of channel. Pass packet to receiving side rdt

deliver_data(): called by rdt to deliver data to upper layer

Transport Layer

incrementally develop sender, receiver sides of reliable data transfer protocol (rdt)
consider only unidirectional data transfer
but control info will flow on both directions!
specify sender and receiver’s responses

Reliable data transfer: getting started
Transport Layer

rdt1.0: reliable transfer over a reliable channel
underlying channel is perfectly reliable
no bit errors
no loss of packets
For sender, receiver:
sender sends data into underlying channel
receiver reads data from underlying channel

Transport Layer

underlying channel may flip bits in packet
use checksum to detect bit errors
the question: how to recover from errors:
acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK
negative acknowledgements (NAKs): 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
receiver feedback: control msgs (ACK,NAK) rcvr->sender
rdt2.0: channel with bit errors

How do humans recover from “errors”
during conversation?
Transport Layer

underlying channel may flip bits in packet
use checksum to detect bit errors
the question: how to recover from errors?
acknowledgements (ACKs): receiver explicitly tells sender that pkt received is OK
negative acknowledgements (NAKs): receiver explicitly tells sender that pkt received has errors
sender retransmits pkt upon receipt of NAK
new mechanisms in rdt2.0 (beyond rdt1.0):
error detection
feedback: control msgs (ACK,NAK) from receiver to sender
rdt2.0: channel with bit errors

Transport Layer

underlying channel may flip bits in packet
new mechanisms in rdt2.0 (beyond rdt1.0):
error detection
use checksum to detect bit errors
feedback: receiver sends control msgs to sender
operation with no errors
acknowledgements (ACKs): receiver explicitly tells sender that pkt received is OK
error scenario
negative acknowledgements (NAKs): receiver explicitly tells sender that pkt received has errors
sender retransmits pkt upon receipt of NAK
rdt2.0: channel with bit errors

Transport Layer

rdt2.0 has a fatal flaw!
what happens if ACK/NAK corrupted?
sender doesn’t know what happened at receiver!
can’t just retransmit: possible duplicate

handling duplicates:
sender retransmits current pkt if ACK/NAK corrupted
sender adds sequence number to each pkt
receiver discards (doesn’t deliver up) duplicate pkt

stop and wait
sender sends one packet,
then waits for receiver
Transport Layer

rdt2.1: discussion
seq # added to pkt
two seq. #’s (0,1) will suffice. Why?
must check if received ACK/NAK corrupted
sender must “remember” whether “expected” pkt should have seq. # of 0 or 1

store the last pkt with seq. #
must check if received pkt is duplicate
check whether 0 or 1 is expected pkt seq. #
note: receiver can not know if its last ACK/NAK is received OK at sender

Transport Layer

rdt2.2: a NAK-free protocol
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
duplicate ACK at sender results in same action as NAK: retransmit current pkt
Transport Layer

rdt3.0: channels with errors and loss
new assumption: underlying channel can also lose packets (data, 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 is received in this time
if pkt (or ACK) is just delayed (not lost):
retransmission will be duplicate, but seq. # already handles this
receiver must specify seq # of pkt being ACKed
requires countdown timer

Transport Layer

(a) no loss

(b) packet loss

resend pkt1
rdt3.0 in action

Transport Layer

rdt3.0 in action

(detect duplicate)

resend pkt1
(detect duplicate)

(d) premature timeout/ delayed ACK

resend pkt1

(detect duplicate)
Transport Layer

rdt3.0: stop-and-wait operation

first packet bit transmitted, t = 0

last packet bit transmitted, t = L / R

first packet bit arrives

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

U sender: utilization – fraction of time sender is busy sending
Transport Layer

Performance of rdt3.0
rdt3.0 is correct, but performance is poor
e.g.: 1 Gbps link, 15 ms prop. delay, 8000 bit packet:

if RTT=30 msec, 1KB pkt every 30 msec
=> 33KB/sec throughput over 1 Gbps link
network protocol limits use of physical resources!

109 bits/sec

8 microsecs
Transport Layer

Pipelined protocols
pipelining: sender allows multiple, “in-flight”, yet-to-be-acknowledged pkts to be transmitted sequentially
range of sequence numbers must be increased ([0,1] => [0,N-1])
buffering at sender and/or receiver

Transport Layer

Pipelining: increased utilization

first packet bit transmitted, t = 0

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!

Transport Layer

Pipelined protocols: overview
Go-Back-N:
sender can have up to N unacked packets in pipeline
receiver only sends cumulative ACK
doesn’t ack packet if there’s a gap
sender has timer for oldest unacked packet
when timer expires, retransmit all unacked packets
Selective Repeat:
sender can have up to N unacked packets in pipeline
rcvr sends individual ACK for each packet

sender maintains timer for each unacked packet
when timer expires, retransmit only that unacked packet

two pipelined protocols: Go-Back-N, Selective Repeat
Transport Layer

Stopped here

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

ACK(n): acks all pkts up to seq # n, including seq # n – “cumulative ACK”
may receive duplicate ACKs (see receiver)
timer set for oldest in-flight pkt
timeout(n): retransmit pkt n and all higher seq # pkts in window

Transport Layer

ack-only: always send ACK for correctly-received pkt with highest in-order seq #
may generate duplicate ACKs
need only remember expectedseqnum
out-of-order pkt:
discard (don’t buffer): no receiver buffering!
re-ack pkt with highest in-order seq #
GBN: receiver

Transport Layer

GBN in action
send pkt0
send pkt1
send pkt2
send pkt3

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

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

Transport Layer

Selective repeat
receiver individually acknowledges all correctly received pkts
buffers pkts, as needed, for eventual in-order delivery to upper layer
sender only resends pkts for whose ACK not received
sender maintains timer for each unacked pkt
sender window
N consecutive seq #’s
limits seq #s of sent, unacked pkts
Transport Layer

Selective repeat: sender, receiver windows

Transport Layer

Selective repeat
data from above:
if next available seq # is in window, send pkt
timeout(n):
resend pkt n, restart timer
ACK(n) in [sendbase,sendbase+N-1]:
mark pkt n as received
if n is smallest unacked pkt, advance window base to next unacked seq #

pkt n is 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 is in [rcvbase-N,rcvbase-1]
send ACK(n)
otherwise:

Transport Layer

Selective repeat in action
send pkt0
send pkt1
send pkt2
send pkt3

receive pkt0, send ack0
receive pkt1, send ack1

receive pkt3, buffer,
rcv ack0, send pkt4
rcv ack1, send pkt5

pkt 2 timeout
send pkt2

receive pkt4, buffer,
receive pkt5, buffer,
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

record ack4 arrived
record ack5 arrived

Q: what happens when ack2 arrives?
Transport Layer

Selective repeat:
seq #’s: 0, 1, 2, 3
window size=3
receiver window
(after receipt)
sender window
(after receipt)

0 1 2 3 0 1 2

retransmit pkt0

0 1 2 3 0 1 2

will accept packet
with seq number 0

0 1 2 3 0 1 2

will accept packet
with seq number 0

0 1 2 3 0 1 2
(a) no problem

receiver can’t see sender side.
receiver behavior identical in both cases!
something’s (very) wrong!

receiver sees no difference in two scenarios!

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts