Transcript Note - Academic Csuohio

EEC-484/584
Computer Networks
Lecture 13
Wenbing Zhao
[email protected]
(Part of the slides are based on Drs. Kurose &
Ross’s slides for their Computer Networking book)
2
Outline
• Sliding window protocols
• UDP
• TCP
– Segment header structure
– Connection management
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
3
Go Back n
• Sender
– Stores all packets in output buffer
– Must get acks in order in which packets are sent
• Receiver
– Discards all packets following lost or damaged one
• Works well
– If transmission errors rare and few retransmissions
– If lot of traffic in both directions
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
4
Selective Repeat
• Receiver accepts and buffers packets following
lost or damaged packets
• Both sender and receiver maintain windows
– Sender’s window starts at 0, grows to MAX SEQ
– Receiver’s window fixed at MAX SEQ
• Receiver has buffer reserved for each seq num
in its window
0
1
Fall Semester 2008
2
3
4
5
6
7
EEC-484/584: Computer Networks
Wenbing Zhao
5
Selective Repeat
• When packet arrives, receiver checks if seq num in
window
• If so and if not already received, this packet is accepted
and stored
• If all lower numbered packets delivered, this packet is
delivered as well
5
0
1
2
3
Fall Semester 2008
4
5
3
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
EEC-484/584: Computer Networks
Wenbing Zhao
6
Selective Repeat
• If no reverse traffic before timer goes off, separate ack is
sent
• When receiver suspects error, sends NAK back to sender
(request for retransmission)
• Two circumstances that trigger NAK
– Damaged packet arrives
– Packet other than expected one arrives, suspect expected one is
lost
• Receiver sends only one NAK for packet expected
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
7
Non-Sequential Receive Problem
• New range of valid sequence numbers for
receiver can overlap old range
• Overlap can contain duplicates
• Example: n = 3-bit seq num (8 possible numbers,
0 through 7, back to 0)
0
1
Fall Semester 2008
2
3
4
5
6
7
0
1
2
EEC-484/584: Computer Networks
3
4
5
6
7
Wenbing Zhao
8
Non-Sequential Receive Problem
• Sender sends 0,1,2,3,4,5,6
• Receiver
– Receives 0,1,2,3,4,5,6
– Sends ack but ack gets lost
– Expects to receive 7,0,1,2,3,4,5
0
1
2
3
4
5
6
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
9
Non-Sequential Receive Problem
• Sender times out, retransmits 0,1,2,3,4,5,6
• Receiver checks 0 is in new window, thinks new 0
because has sent ack for old 6, waits for 7
0
1
Fall Semester 2008
2
3
4
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
5
6
EEC-484/584: Computer Networks
7
Wenbing Zhao
10
Non-Sequential Receive Problem
• Sender receives ack for 0-6, sends 7
• Receiver receives 7, delivers 7 and
old 0 (as new 0 !)
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
11
Non-Sequential Receive Problem
• The problem is caused by the overlap of
sequence number between the new receiving
window and the old receiving window
0
1
2
3
4
5
6
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
Overlap
Fall Semester 2008
Overlap
EEC-484/584: Computer Networks
Wenbing Zhao
12
UDP: User Datagram Protocol
• “No frills,” “bare bones” Internet transport protocol
• “Best effort” service, UDP segments may be:
– Lost
– Delivered out of order to app
• Connectionless:
– No handshaking between UDP sender, receiver
– Each UDP segment handled independently of
others
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
13
Why is There a UDP?
• No connection establishment (which can
add delay)
• Simple: no connection state at sender and
receiver
• Small segment header
• No congestion control: UDP can blast
away as fast as desired
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
14
UDP
• Often used for streaming
multimedia apps
Length, in
– Loss tolerant
bytes of UDP
segment,
– Rate sensitive
• Other UDP uses
32 bits
source port #
dest port #
length
checksum
including
header
– DNS
– SNMP
• Reliable transfer over UDP:
add reliability at application
layer
Fall Semester 2008
EEC-484/584: Computer Networks
Application
data
(message)
UDP segment format
Wenbing Zhao
15
UDP Checksum
Goal: detect “errors” (e.g., flipped bits) in
transmitted segment
Sender:
Receiver:
• treat segment contents as • compute checksum of
received segment
sequence of 16-bit integers
• check if computed
• checksum: addition (1’s
checksum equals
complement sum) of
checksum field value:
segment contents
– NO - error detected
• sender puts checksum
– YES - no error detected. But
value into UDP checksum
maybe errors nonetheless?
field
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
Internet Checksum Example
• When adding numbers, a carryout from the most
significant bit needs to be added to the result
• Example: add two 16-bit integers
1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
sum
checksum
1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
To know more:
http://www.netfor2.com/udpsum.htm
http://www.netfor2.com/checksum.html
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
16
17
TCP: Overview
• Full duplex data:
• Point-to-point:
– One sender, one receiver
• Reliable, in-order byte
steam:
– No “message boundaries”
• Pipelined:
– TCP congestion and flow
control set window size
• Send & receive buffers
– Bi-directional data flow in
same connection
– MSS: maximum segment
size
• Connection-oriented:
– Handshaking (exchange
of control msgs) init’s
sender, receiver state
before data exchange
• Flow controlled:
– Sender will not overwhelm
receiver
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
18
TCP: Overview
• TCP connection is byte stream, not message stream, no
message boundaries
• TCP may send immediately or buffer before sending
• Receiver stores the received bytes in a buffer
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
19
TCP Segment Structure
URG: urgent data
(generally not used)
ACK: ACK #
valid
PSH: push data now
(generally not used)
RST, SYN, FIN:
connection estab
(setup, teardown
commands)
Internet
checksum
(as in UDP)
Fall Semester 2008
32 bits
source port #
dest port #
sequence number
acknowledgement number
head not
UA P R S F
len used
checksum
Receive window
Urg data pnter
Options (variable length)
application
data
(variable length)
EEC-484/584: Computer Networks
counting
by bytes
of data
(not segments!)
# bytes
rcvr willing
to accept
A TCP
segment must
fit into an IP
datagram!
Wenbing Zhao
20
The TCP Segment Header
• Source port and destination port: identify local end points
of the connection
– Source and destination end points together identify the connection
• Sequence number: identify the byte in the stream of data
that the first byte of data in this segment represents
• Acknowledgement number: the next sequence number
that the sender of the ack expects to receive
– Ack # = Last received seq num + 1
– Ack is cumulative: an ack of 5 means 0-4 bytes have been
received
• TCP header length – number of 32-bit words in header
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
21
The TCP Segment Header
• URG – indicates urgent pointer field is set
• Urgent pointer – points to the seq num of the last byte in a
sequence of urgent data
• ACK – acknowledgement number is valid
• SYN – used to establish a connection
– Connection request: ACK = 0, SYN = 1
– Connection confirm: ACK=1, SYN = 1
• FIN – release a connection, sender has no more data
• RST – reset a connection that is confused
• PSH – sender asked to send data immediately
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
22
The TCP Segment Header
• Receiver window size –number of bytes that may
be sent beyond the byte acked
• Checksum – add the header, the data, and the
conceptual pseudoheader as 16-bit words, take 1’s
complement of sum
– For more info: http://www.netfor2.com/tcpsum.htm
http://www.netfor2.com/checksum.html
• Options – provides a way to add extra facilities not
covered by the regular header
– E.g., communicate buffer sizes during set up
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
23
TCP Sequence Numbers and ACKs
Host A
Sequence numbers:
– byte stream “number” of
first byte in segment’s
data
User
types
‘C’
host ACKs
receipt of
‘C’, echoes
back ‘C’
ACKs:
– seq # of next byte
expected from other
side
– cumulative ACK
Host B
host ACKs
receipt
of echoed
‘C’
simple telnet/ssh scenario
Fall Semester 2008
EEC-484/584: Computer Networks
time
Wenbing Zhao
24
TCP Connection Management
TCP sender, receiver establish “connection”
before exchanging data segments
• Initialize TCP variables:
– Sequence numbers
– Buffers, flow control info (e.g. RcvWindow)
• Client: connection initiator
Socket clientSocket = new
Socket("hostname","port number");
• Server: contacted by client
Socket connectionSocket = welcomeSocket.accept();
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
25
TCP Connection Management
Three way handshake:
Step 1: client host sends TCP SYN segment to server
– specifies initial sequence number
– no data
Step 2: server host receives SYN, replies with SYN/ACK
segment
– server allocates buffers
– specifies server initial sequence number
Step 3: client receives SYN/ACK, replies with ACK
segment, which may contain data
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
26
TCP Connection Management
client
Three way handshake:
• SYN segment is
considered as 1 byte
• SYN/ACK segment is also
considered as 1 byte
Fall Semester 2008
connect
EEC-484/584: Computer Networks
server
accept
Wenbing Zhao
27
TCP Connection Management
client
Closing a connection:
server
close
client closes socket:
clientSocket.close();
Step 1: client end system sends
close
Step 2: server receives FIN,
replies with ACK. Closes
connection, sends FIN.
timed wait
TCP FIN control segment to
server
closed
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
28
TCP Connection Management
client
Step 3: client receives FIN,
replies with ACK.
server
closing
– Enters “timed wait” - will
respond with ACK to
received FINs
closing
Step 4: server, receives ACK.
Note: with small modification,
can handle simultaneous FINs
timed wait
Connection closed.
closed
closed
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao
29
Exercise
• A process at host A wants to establish a TCP connection
with another process at host B. Assuming that host A
chooses to use 1628 as the initial sequence number,
and host B chooses to use 3217 as the initial sequence
number for this connection, show the segments involved
with the connection establishment process. You must
include the following information for each such segment:
(1) sequence number, (2) acknowledgement number (if
applicable), (3) the SYN flag bit status, and (4) the ACK
flag bit status.
Fall Semester 2008
EEC-484/584: Computer Networks
Wenbing Zhao