Transcript Data Modeling - Hiram College

Transport Layer
CPSC 363 Computer Networks
Ellen Walker
Hiram College
(Includes figures from Computer Networking by Kurose & Ross, © Addison Wesley
2002)
Internet Layers
• Application
• Transport
– provides logical connections between processes
running on different computers
• Network
• Data Link
• Physical
Transport Layer Protocols
• UDP (User Datagram Protocol)
– Unreliable
– Connectionless
• TCP (Transmission Control Protocol)
– Reliable
– Connection-oriented
– Flow control and congestion control
• Both depend on IP (Network Layer), which is “best
effort” -- no guarantees of in-order delivery, or of
delivery of all segments!
Services Provided by Transport
Layer
• UDP and TCP
– Multiplexing & Demultiplexing (combine / split
messages for different processes on the same
host, according to port number)
– Error Detection
• TCP only
– Flow control, sequencing, handshaking to ensure
reliable transfer
– Congestion control - regulating rate at which
sender can add traffic to the network
UDP vs. TCP
• UDP for network infrastructure (e.g. routing
protocol, DNS)
– Need info when net is congested!
UDP vs. TCP (cont’d)
• Multimedia (e.g. streaming files) and Internet
Telephony use UDP or TCP with proprietary
protocols
–
–
–
–
Can tolerate some packet loss
Congestion control causes poor performance
BUT need to be good ‘net citizen’
AND security blocks on UDP
UDP Segment
• Destination port
chooses a socket
• Source port for
“return address”
• Checksum for
error checking
• Application never
sees the header
Source port#
Dest. Port #
Length
Checksum
data… data… data… data…
Sending a UDP message
1. Construct the Header
•
•
Insert appropriate source and destination port
numbers
Calculate checksum
•
•
•
Divide data into “words” e.g. 16 bits
Add them all up (overflow wraps around!)
Flip each bit
2. Pass frame to Network layer for delivery to
the destination host.
Receiving a UDP Message
1. Receive frame from Network layer.
2. Check for errors
•
•
Add up all “words” and the checksum.
If the sum is not 1111111111111111, there is an error.
3. If no error, pass the message to the appropriate
socket, based on port number
4. If there is an error, either discard the frame, or pass
it to the socket with a warning.
TCP is More Complex
• Multiplexing/demultiplexing based on source
port, destination port, source address, and
destination address
– Different sources may go to different sockets
– Special socket for new connections (no process
yet)
• If the new connection is accepted a socket (and process)
is created for it.
• TCP provides additional services (reliable
transport)
State machine
• State machine abstraction
– At any time, the process is in a “state”
– Each time an “event” happens, the process takes
an “action” and goes to the next state
– We can describe the entire algorithm as a diagram
where each state has an arrow for each
event/action pair to the next appropriate state
State Machine for a Kitten
Happy
Food available / Eat
Hungry
Toys available / Play
Sleeping
X hrs passed / Awaken
State Machine: Send/Receive #1
Sender
waiting
Receiver waiting
Data (from appl) to send /
make packet & send to
network
Data received (from network) /
extract data & deliver to appl
Assumption: network is completely reliable
State Machine: Send/Receive #2
Data (from appl) to send /
waiting make packet & send to network
Sender
for appl
Receive NAK from network/
Resend packet
waiting
Receive ACK from network /
for ACK
(nothing to do)
Receiver waiting
Receive OK packet / send ACK & deliver data
Receive bad packet / send NAK
Assumption: all frames delivered, but some are corrupt.
Problem: What if ACK / NAK is corrupt?
State Machine: Send #2.1
Data (from appl) to send /
wait
make packet 0 & send to network
for appl
Receive corrupt or NAK/
0
wait Resend packet
for ACK
Receive ACK from network /
0
(nothing to do)
Receive ACK from network /
(nothing to do)
Receive corrupt or NAK/
wait Resend packet
wait
for ACK
for appl
1
1
Data (from appl) to send /
make packet 1 & send to network
Comments on Send 2.1
• Each frame now has a sequence number (0
or 1)
• Treat a corrupt packet received as NAK
– If it was really NAK, no harm done
– If it was really ACK, extra data will be sent
• Sequence numbers allow duplicate packets
to be recognized (2 0’s or 1’s in a row)
State Machine: Receive #2.1
Receive OK packet 1 / send ACK
wait 0
Receive corrupt packet / send
NAK
Receive OK packet 0/
send ACK& deliver
data
Receive OK packet 1/
send ACK & deliver
data
wait 1
Receive OK packet 0/ send ACK
Receive bad packet/ send NAK
ACK all non-corrupt packets, but only deliver packets with
the correct sequence number to the application.
V. 2.2 Uses only ACK’s
• Each ACK contains the sequence number of the
packet being acknowledged
• Instead of NAK, resend last ACK
• If the ACK is for the wrong packet, it’s really a NAK
• Assume packets 0 (OK), 1 (corrupt)
–
–
–
–
–
Packet 0 sent
Packet 0 received, ACK 0 sent
ACK 0 received, packet 1 sent
Packet 1 corrupt, ACK 0 (last ACK) resent
ACK 0 received, packet 1 resent (like NAK from before)
Summary So Far
• Protocol 1: perfect transmission channel
– Outside of data, no communication needed
• Protocol 2: some packets are corrupt
– Each packet must be acknowledged
– Until ACK received, no new packets can be sent
– Packet sequence numbers avoid problems with
corrupt acknowledgement message
– ACK vs. NAK or ACK1 vs ACK0
• Protocol 3: some packets get lost
Packet Loss in v. 2.2
• If the data is lost
– Receiver never receives the data; stuck in wait 0
or wait 1 state
– Sender therefore doesn’t get ACK, stuck in wait
ACK 0
• If the ACK is lost
– Receiver received the data, sent ACK
– Sender doesn’t get ACK state, stuck in wait ACK 0
• No additional data can be sent!
Adding a Timer
• If we had to wait “too long” assume packet
was lost
– Might not really be lost, might be just delayed
– “Lost” packets are resent
– If not lost, they are duplicates, will be ignored as
for corrupt packets
• How long to wait?
– Minimum is 1 RTT
– Too short -> many packets are duplicated
– Too long -> overall transmission is slowed
State Machine: Send #3.0
Data (from appl) to send /
make packet 0 & send to network
wait
Start timer
Receive corrupt or ACK 1/
for appl
(nothing to do)
0
wait
for ACK
Receive ACK from network /
Timeout/
0
(nothing to do)
Resend packet
Timeout/
Resend packet
Receive ACK from network /
(nothing to do)
Receive corrupt or ACK 0/
wait (nothing to do)
for ACK
1
Data (from appl) to send /
make packet 1 & send to network
Start timer
wait
for appl
1
Operation of Protocol 3.0
(fig. 3.16a,b)
Operation of Protocol 3.0
(Fig. 3-16c,d)
Summary: Components of Reliable
Data Transfer
• Checksum - to recognize a corrupt packet
• Alternating sequence numbers - to recognize
duplicate packets
• Acknowledgements - to communicate when a
packet was successfully received
• Timer - to determine when a packet or its
acknowledgement was lost
Pipelined Reliable Data Transfer
• Protocol 3.0 is a “stop and wait” protocol - no new
packet can be sent until the previous one is
successfully acknowledged
• Both sender and receiver spend most of their time
waiting!
– Utilization is (L/R) / (L/R + RTT), on the order of 0.025%!
• To pipeline (send more packets while waiting for an
acknowledgement)
– Increase available sequence numbers
– Buffer packets that have been sent but not acknowledged (in
case they need to be resent)
– Receiver might also need a buffer…
Go Back N Protocol
• Last acknowledged packet may be no more than N
(window size) less than last sent packet
• If difference gets to N, stop sending until it gets
smaller
• If nothing happens until timeout, resend all
unacknowledged packets
• Acknowledge packet only if all its predecessors have
been received. Otherwise, drop it.
Actions for Go Back N Sender
• Initialize
– base = 1
– nextseqnum = 1
• To send a packet
– If (nextseqnum < base + N)
– build a packet (nextseqnum)
– send the packet
– if (base == nextseqnum) start a timer
– nextseqnum++
Actions for Go Back N Sender (cont)
• When a valid acknowledgement is received
– base = ack seqnum + 1 //first unack’ed packet
– If (base == nextseqnum)
–
stop timer // all sent packets received
– Else start timer
• When the timer goes off
– start timer
– Resend all packets from base through
nextseqnum–1
Actions for Go Back N Receiver
• Initialize:
– expectedseqnum = 1
– Make ACK 0 packet (in case pkt 1 is corrupt)
• When packet # expectedseqnum is received
– Extract and deliver data to application
– Make ACK expectedseqnum packet & send it
– expectedseqnum++
• When packet is out-of-sequence or corrupt
– Resend last ACK
Example: Go
Back 4 (3.22)
Go-Back-N Protocol
Demo
Summary: Effects of Go-Back-N
• Sender cannot have more than N packets
outstanding.
• Sender retransmits all packets until they are
acknowledged. (LOTS of retransmission!)
• Out of order packets are ignored -- receiver
gets packets in order.
• Corrupt packets are not acknowledged.
• In short, reliable transmission across an
unreliable link!
Selective Repeat
• Each packet is separately acknowledged
(including out-of-order ones)
• Receiver buffers out-of-order packets until
their predecessors are available
• Like GBN, limited # of unack’ed packets
(window size)
• Sender resends each individual packet when
it “times out” without an ACK
Actions for SR Sender
• Initialize
– send_base=1; next_seqnum=1
• Data from above
– If next_seqnum-send_base < window_size, send the packet
and start its timer
• When ACK is received
– Mark packet as received
– If it is send_base, update send_base to first unacked packet
• On timeout for a packet
– Resend the packet
Actions for SR Receiver
• When a packet is received
–
–
–
–
–
–
–
–
If it is < rcv_base, ACK the packet
If it is already ACKed, ACK it again
If it is rcv_base
send it to app
send all subsequent ACKed packets to app
set rcv_base to first unACKed packet
If it is not ACKed but is in window, save it
If it is > rcv_base + winsize, ignore it
Example (Fig 3.26)
Need Enough Sequence Numbers
GBN vs. SLR tradeoffs
• Both have limited number of outstanding
packets
• Both require resends on timeout
• GBN resends ACKed packets, SLR doesn’t
• SLR tracks non-sequential ACKed packets,
GBN doesn’t
• SLR buffers out-of-order packets, GBN
doesn’t
Overview of TCP Communication
• Connection is opened (3 messages)
– Request (SYN1), ACK+Grant (SYN 1), ACK (SYN 0)
• Data is sent
– Application puts data into send buffer
– Segments created & sent through network layer
• Grab MaxSegmentSize (MSS) bits from buffer
• Wrap with a TCP header
• Data is received
– Data extracted from segment into receive buffer
– Application takes data from receive buffer
• Connection is closed (4 messages)
– FIN, ACK (client to server); FIN, ACK (server to client)
About TCP Connections
• Connection is maintained only at the end
hosts, not intermediate nodes
– Not virtual circuit!
• Connection is full-duplex
– Both ends can send and receive at the same time
• TCP is a point-to-point connection
– Two hosts, no multicasting
TCP Segment Structure (3.29)
Sequence and Acknowledgement
Numbers
• Sequence Number
– Sequence number of current segment
– As in Go Back N protocol
– Actually counts bytes in message, not segment #
• Acknowledgement Number
– Sequence number of next expected segment
– As in Go Back N, all segments with lower numbers
have been received (cumulative ACK)
– TCP RFC’s do not specify whether out-of-order
packets are buffered
Telnet Example: Full Duplex (3.31)
Host B echoes each
byte from host A
ACK “piggybacked”
on next data packet
Round Trip Time
• Time from transmittal of message to receipt of ACK
• Minimum 2*(sum of 4 delays from ch. 1)
• But we also need to consider
– Waiting time when too many packets are outstanding
– Retransmission time
• Depends on traffic, so we have to measure it
– Take running average over last k packets (not equally
weighted)
• Choose timeout interval greater than Expected RTT
Flow Control
• Necessary to avoid receiver overflowing its
buffer
– No room in buffer -> packet loss!
• Goal: match sender’s rate to receiver’s rate
• Sender maintains estimate of receiver’s
available space (Receive window)
• Receiver communicates information about
available space in each message
Calculating RcvWindow
• Receiver
– Computes number of available bytes in buffer
• RcvWindow = RcvBuffer – [LastByteRcvd – LastByteRead]
– Transmits this value along with each ACK
• Sender
– Computers number of unacknowledged bytes in buffer
• LastByteSent – LastByteAcked
– If this is > RcvWindow from receiver, send only 1 byte.
– Example: Flow Control Applet
Why One Byte?
• If host A doesn’t send anything, then host B
won’t ACK
• So when host B’s buffer empties, it won’t be
able to tell host A (since RcvWindow is sent
on ACK)
• Therefore, host A keeps trying one-byte
packets to give host B something to ACK
Costs of Congestion
• Large queuing delays are encountered as the packet
arrival rate nears the link capacity
• Senders must retransmit to compensate for lost
packets due to buffer overflow (increasing the total
number of packets)
• As delays increase, senders resend even more
packets due to timeouts!
• When a packet is dropped along a multi-link path, the
work (and buffer space) already spent on it is “lost”
Congestion Control
• End-to-end
– Network provides no explicit support
– When segments are lost (timeout), hosts decrease window
size (don’t let their buffers fill up)
– TCP does this; min of CongWindow and RcvWindow
• Slow start - small window, doubles until congested
• Network assisted
– Routers send information back to hosts about congestion
– Choke packet: “I’m congested!”
– Not (yet) used by TCP; used in ATM
TCP Congestion Control
• TCP sender “perceives” congestion on
network
– If congested, reduce send rate
– If not congested, increase send rate
• Requires:
– Ability to regulate send rate
– Ability to perceive congestion
– Algorithm for adjusting send rate “smoothly”
Regulating Send Rate
• Sender has “CongWin” (congestion window)
variable
– Amount of unacknowledged data <= CongWin
– (also) Amount of unack’d data <= RcvWin from
flow control
– Therefore, amt of unack’d data
<=min(CongWin,RcvWin)
• Like flow control; if CongWin reached, stop
sending more data!
Perceiving Congestion
• “Loss event”
– Timeout
– 3 Duplicate ACKs
• Indicates congestion
– Buffer overflow causes packet loss
• Loss events are counted and cause
adjustment of send rate (by adjusting
CongWin)
TCP Congestion Control Algorithm
• Additive Increase, Multiplicative Decrease
– Each loss event cuts CongWin in half (multiply)
– When no loss, increment by 1 MSS every RTT (add)
• Slow start
– Initialize CongWin to 1MSS
– Double every RTT (until first loss), then AIMD
• Reaction to timeout events
– Revert to slow start after timeout (vs. 3 duplicate ACKs)
– Controlled by Threshold (TCP Tahoe vs. TCP Reno)
– TCP Reno reverts to AIMD after 3 dupl. ACKs)
Example: CongWin (in MSS units)
• Slow start (loss after 10RTT)
– 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024
• AIMD (loss after 20 RTT)
– 512, 513, 514 … 520, 521, 522 (loss)
– 261, 262, 263 … 279, 280, 281 (loss)
etc.
Summary: Congestion & Flow
Control
• Flow control is between sender & receiver
– Receiver provides info (Receive Window) in each
ACK packet
• Congestion control is across network
– Sender tracks Congestion Window, increasing
when no loss and decreasing when loss
• Cannot ever have more than Receive
Window or Congestion Window packets
outstanding (sender stops in this case)