Transcript ppt - Computer Science

TCP
section 6.5
(Read this section!)
1 Mar 2007
CS 360 – Spring 2007
Pacific University
Transport Layer
• Key interface between applications and the network
• What does reliable really mean?
– Network Layer (IP) does not guarantee
• delivery of packets
• in order delivery of packets
– RFC:
“The TCP must recover from data that is damaged, lost,
duplicated, or delivered out of order…”
“As long as the TCPs continue to function properly and the
internet system does not become completely partitioned, no
transmission errors will affect the correct delivery of data. TCP
recovers from internet communication system errors.”
CS 360 – Spring 2007
Pacific University
TCP
• Transport layer (TCP) does guarantee (RFC 793)
– delivery
– in order delivery
• Provides
– full duplex connections
– point-to-point (exactly two end points, no multicasting)
CS 360 – Spring 2007
Pacific University
TCP Protocol Basics
• Each byte in the stream has its own 32-bit sequence
number
– on a 56 kbps phone line, it takes 1 week (plus) to cycle through
– “At 100 megabits/sec, the cycle time is 5.4 minutes” RFC 793
– “Maximum Segment Lifetime, the time a TCP segment can exist in
the internetwork system. Arbitrarily defined to be 2 minutes.”
RFC 793 Not really enforced, assumed
– time to live set to one minute or 00111100
• TTL set in IP header (8 bit field)
• Basic unit of transfer is the TCP segment
–
–
–
–
–
sometimes called a packet (incorrectly)
fixed 20-byte header
optional header extension
data
max segment size:
• 64KB IP payload
• networks MTU (maximum transfer unit) (~1500 bytes for Ethernet)
CS 360 – Spring 2007
Pacific University
CS 360 – Spring 2007
Pacific University
TCP Options
16-bit max segment size – 64KB
• If this is not specified the default size is 536 bytes
– RFC 879
• Both sides send this option to determine segment size
– both sides must use the same segment size
CS 360 – Spring 2007
Pacific University
Sliding Window
• Sliding window protocol used to manage
flow/retransmission
– waits for acknowledgement (ACK) or a timeout
– retransmit if the ACK times out
• Acknowledgement number denotes the next byte to be
received
– when ACK 1138 is sent
• all bytes 0-1137 have been received
– an ACK may contain data
• piggybacking
• Window size denotes how many more bytes may be sent
–
–
–
–
16-bit field
really denotes how many bytes may be in transit at one time
zero is a legitimate window size
ACK and Window size are decoupled
• variable window sizeCS 360 – Spring 2007
Pacific University
Tanenbaum, Figure 6-33, p543
CS 360 – Spring 2007
Pacific University
Buffers
• Senders may buffer data for any amount of time before
sending it
• Receivers may delay an ACK as well
• This could save bandwidth
• Could be bad if you are typing on a remote shell
• What does it cost to send one byte of data?
CS 360 – Spring 2007
Pacific University
Nagle
• When data comes in to the buffer one byte at a time
–
–
–
–
–
–
–
send first byte
buffer data until the ACK is received
send all buffered data
buffer until the ACK
repeat
send extra packets if the buffer fills 1/2 way before the ACK
good for fast typing on a slow network
• Sometimes needs to be disabled
– when might this be bad?
CS 360 – Spring 2007
Pacific University
Silly Window Syndrome
• Sender produces large chunks of data
• Receiver eats the data a byte at a time
What is the problem?
How can we fix this?
Tanenbaum, Figure 6-35, p546
CS 360 – Spring 2007
Pacific University
No one will ever need more than 64KB!
• Max window size: 64 KB.
– Goal: keep the pipe as full as possible without causing too much
network congestion!
• On a T3 line (44.736 Mbps)
–
–
–
–
12 msec to output 64KB
50 msec propagation delay for transcontinental fiber
How often is the sender idle?
worse on a satellite link (why?)
• Hack (Fix) RFC 1323
– we cannot change the size of the 16-bit field
– but we can change what it represents
– adds a TCP option that allows the 16-bit field to be shifted left up
to 14 bits
• for a window size of up to 230
• most TCP implementations now support this
CS 360 – Spring 2007
Pacific University
Connection Establishment
• 3-way handshake
• Uses the SYN and ACK bit
fields in the TCP header
• Security
– common Denial of Service attack
is the SYN flood
– send a SYN
– server sends a SYN ACK
• allocates memory to track the
connection!
– client never sends the ACK
– server holds memory until timeout
– generating many SYNs quickly is
easy
– how would you implement this?
Tanenbaum, Figure 6-31, p540
• you don’t want to get caught
• how can we prevent this?
CS 360 – Spring 2007
Pacific University
Initial Sequence Number
• Initial sequence number is not zero
–
–
–
–
–
Initial Sequence Number Generator selects the ISN
32 bit clock with a tick every 4 microseconds
rolls over every 4.55 hours
this allows a connection to be reused quickly
no lingering packets in the network can show up with a valid
sequence number
• why might packets linger in the network?
• If a TCP service crashes it is to refrain from sending any
packets for a MSL
– if it does retain its last used sequence number, no need to wait
CS 360 – Spring 2007
Pacific University
Connection Release
• One or both sides send a packet with the FIN bit set
– “I will send no more data”
– can still receive data
– other side needs to send an ACK
• After two FINs are sent the connection is closed by each
end
– two ACKs must be received
• After a FIN if nothing is received after a period of time
the connection times out
– two maximum segment lifetimes
CS 360 – Spring 2007
Pacific University
Tanenbaum, Figure 6-33, p543
CS 360 – Spring 2007
Pacific University
Timers & Retransmission
• Send segment & start timer
– if the timer goes off before the ACK is received, retransmit
• How long should the timeout interval be?
– what factors do we need to consider?
– what makes this hard?
– what happens if we set the
timerout to T1? T2?
Tanenbaum, Figure 6-38, p551
CS 360 – Spring 2007
Pacific University
Timers
• Each connection keeps a value RTT
– estimated Round Trip Time
– updated after every ACK
• M = round trip time of the last ACK
• RTT = *RTT + (1 -  )*M
–  is a smoothing factor
– typically 7/8
• Timeout:
*RTT
– early implementations set  to 2. why?
– not flexible enough? why?
• Jacobson proposed making  roughly proportional to
standard deviation of the ACK time
– use mean deviation as cheap estimator
– variable named D
CS 360 – Spring 2007
Pacific University
Timers
• D =  * D + (1- ) * | RTT - M|
– Jacobson showed how to do with with only integer
•
•
•
•
add
subtracts
shifts
why is this important?
• Timeout value: RTT + 4 * D
– ACK can be 4 standard deviations late
• initially used 2 but 4 found to be better (experimentally)
• less than 1% timeout on a healthy link
– somewhat arbitrary choice
– easy to implement with shifts!
• When might you get two ACKs for the same segment?
– why might this cause problems?
– solution?
CS 360 – Spring 2007
Pacific University
Other Timers
• Persistence Timer
–
–
–
–
–
receiver sets window size to 0
sender waits
receiver sets window size to 2048 but the packet is lost!
both sides wait for something to happen
the persistence timer tells the sender to probe the receiver if the
receiver has not been heard from in a while
• Keepalive Timer
– if the connection is idle, send a packet to see if the other side is
still connected
– not always used
– adds traffic
CS 360 – Spring 2007
Pacific University
ACKs & Retransmission
• When does the receiver ACK?
– Receive in-order segment with expected sequence number
• all previous data already ACKed
• wait up to 500 msec for next in-order segment
• send ACK
– Receive in-order segment w/ expected seq number
• previous segment no yet ACKed
• send cumulative ACK immediately
• Fast Retransmit (RFC 2581)
– Receive out-of-order segment w/ higher than expected seq number
•
•
•
•
GAP!
send duplicate ACK (for last ACKed segment)
this acts a message to the sender that things are going bad
a “Triple Duplicate ACK” means 3 segments beyond the gap have been
seen (total of 4 ACKs for one segment)
– Receive segment that fills in gap
• send ACK (if this fills in the lower end of the gap)
CS 360 – Spring 2007
Pacific University
Congestion Control
• Some done in Network Layer
• Most done in Transport Layer
– how do you control congestion?
• Law of conservation of packets:
– don’t send new packets until old ones are received
• Dynamically manipulate window size to control how
much data is in the network
• How can we detect congestion in the network?
CS 360 – Spring 2007
Pacific University
CS 360 – Spring 2007
Tanenbaum,
Figure 6-36, p548
Pacific University
Implementation Details
• Receiver Capacity
– receiver window (based on receiver buffer size, load, etc)
• Network Capacity
– congestion window (sender window)
• Use the minimum of the two values
• How do we find the Congestion Window Size?
– Slow Start algorithm
– connection initialization: Congestion Window = Max Segment Size
• how is max segment size determined?
– Send off one segment, if it is ACKed before Timeout
• after the ACK, add 1 max segment size to the window size
– Send off 2 segments
• after EACH ACK, add 1 max segment size to the window size
• what just happened there?
– Continue until timeout or the receiver window size is reached
CS 360 – Spring 2007
Pacific University
A Loss
• What happens when there is a lost packet?
– what does that loss tell us?
– what should we do in response to that?
CS 360 – Spring 2007
Pacific University
More Details
• When a timeout occurs, we reduce the congestion window
(TCP Tahoe)
– set threshold variable: 1/2 the congestion window at TO
– set congestion window to 1 max segment size
• use slow start until congestion window hits threshold
• after that, grow congestion window by 1 max segment size per burst
• TCP Reno (Fast Recovery)
–
–
–
–
after a “Triple Duplicate ACK” loss, Congestion Window = Threshold
no slow start
grow congestion window by 1 max segment size per burst
why do this?
CS 360 – Spring 2007
Pacific University
Tanenbaum, Figure 6-37, p550
CS 360 – Spring 2007
Pacific University
Project Questions
• How do I stress test
my server?
– use the Konsole to
open multiple shells
– start a client in each
shell
– send input to all of
them at once
setsockopt( writeSocket, IPPROTO_TCP, TCP_NODELAY,
SOL_TCP is Linux-specific!
CS 360 – Spring 2007
Pacific University
... )
Safari
• Online books! Search the DB via the Library web site
– Library | Search Databases | Computer Science | Safari
CS 360 – Spring 2007
Pacific University
Safari
• 5 simultaneous users
– be sure to logout when you are done!
– being idle for 10 minutes will log you out
– I will be putting sections of books on electronic reserve
• everyone can access them at once (or print them out)
• about 50 books we (CS profs) have chosen based on
our classes
–
–
–
–
TCP/IP Illustrated (Volume 1 & 2)
UNIX Network Programming
CISCO Manuals
Eclipse handbook/Make guide/Shell Scripting/Linux Guides
• You can print sections from Safari
– HOWEVER, printing large amounts of material is frowned upon
by Safari and may constitute a copyright violation
• this could lead to problems!
CS 360 – Spring 2007
Pacific University
Project Overview- TCP360
• You need to implement a restricted version of TCP
–
–
–
–
–
3 Way Handshake
Graceful connection termination
Send & Receive buffer
Sliding window protocol
Reliable transmission
•
•
•
•
lost packets
corrupt packets
out of order packets
duplicate packets
• You DO NOT need to implement
–
–
–
–
–
–
Persistence timers
Fast retransmit
Congestion control
Estimation of RTT or D
Nagle/fixes for silly window syndrome
TCP Options
CS 360 – Spring 2007
Pacific University
Your server and client will
run on top of this new Transport
Layer.
You must support multiple
TCP360 connections at once
(think about your server)
I will also give you another
application (FTP) to stress test
your TCP360
Project
• The key here is DESIGN!
– how many threads do you have?
– where is your data?
• Plan your implementation very carefully
• To help you along this project will be made of smaller
assignments due on a weekly basis!
• I will provide you a basic design and some code!
CS 360 – Spring 2007
Pacific University
Design Overview (10000 meters)
Client
Server
Application
Application
sock = TCP360socket()
sock = TCP360socket()
TCP360Listen(sock, 99...)
TCP360connect(sock,...,99)
rSock = TCP360accept(sock, 99
TCP360send(sock, data ...)
TCP360recv(rSock, data ...)
TCP360
TCP360
Logical TCP360
Connection
TCP360 port:98
SendToTCPConn(data,...)
TCP360 port:99
NetworkLayerSend(data, IPAddr ...)
NetworkLayer
UDP port:9000
NetworkLayer
UDP port:10001
UDP
udpSock = socket()
udpSock = socket()
bind(udpSock, myUDPport)
sendto(udpSock, data, 9000,
recvfrom(udpSock, data, 9000,..
sendDataToTCP(data)
IPAddr ...)
CS 360 – Spring 2007
Pacific University
Design Overview (1 meter)
Me
You
TCP360Connection
TCP360Connection
MessageQueue
Timer
MessageQueue
NetworkLayer
Alarm
TCP data
TCP data
TCP data
createAlarm()
MessageQueue
recvfrom()
TCP360
CS 360 – Spring 2007
Pacific University
Your First Assignment
• Thread-safe Queue - Due April 6!
– What is a queue? What is a thread safe data structure?
– You need to provide a thread-safe queue to be used for the
message passing
• to make this general, the queue will store void* items
– I will give you a .h file with function prototypes you must
implement
• Project description and .h file will be on the web page tomorrow
• Watch the CS message boards for announcements!
• you may NOT change the .h file, EXCEPT to add mutex variables
– You must provide TWO test cases that show your queue works
properly in a multithread environment
– Due at 6PM! April 6!
CS 360 – Spring 2007
Pacific University
Design Docs
• Design is key!
• Also due on April 6: A short design document for TCP360
–
–
–
–
–
How many threads?
What will each do?
Where will the data be stored?
Who handles retransmits?
The full TCP360 project description will be posted by April 2
• You will need to schedule an individual meeting with me
to discuss your design (April 6-9)
CS 360 – Spring 2007
Pacific University