Transcript Lektion 1-Introduktion

Datornätverk A – lektion 8
Kapitel 11: Flow control and Error control.
(Kapitel 12: Point-to-point access PPP.
Översiktligt.)
11.1 Flow and Error Control
Flow Control (Flödesstyrning)
Error Control (Felhantering)
•
•
Båda dessa funktioner hanteras av vissa
datalänkprotokoll (lager 2), i LLC-sublagret, t.ex.
vid trådlös kommunikation eller vid modem.
End-to-end flödesstyrning och felkontroll
hanteras av transportprotokollet TCP (lager 4).
Flow control
Necessary when data is being sent faster than it can be
processed by receiver to avoid that the receiver’s buffer is
overwhelmed.
Felhantering med hjälp av
felrättande koder
FEC = Forward Error Correction.
Baseras på felrättande istället för felupptäckande koder.
Kräver ingen backkanal.
Två typer:
1. Faltningskoder (convolutional codes).
Ex:Vid Faltningskod med kodtakt (code rate) 1/3 infogas två redundanta bitar
mellan varje bit i nyttomeddelandet. Dessa felrättande bitar beräknas
kontinuerligt för varje inkommande bit i nyttomeddelandet.
2.
Blockkoder (block codes)
Ex: I digital-TV-systemet används en s.k. Read Salomon-kod med
beteckningen RS(204, 188, 8). Det innebär att nyttoinformationen delas
upp i 188 byte stora block. För varje block beräknas en felrättande kod,
som läggs till blocket så att blocket blir 204 byte. Redundanden är alltså
204 – 188 = 16 byte. Koden klarar 8 felaktiga byte.
Felhantering med hjälp av
felupptäckande koder
Alternativ 1: Bortkastning av felaktiga paket.
Alternativ 2: ARQ = Automatic Repeat reQuest
= automatisk omsändning av paket vid bitfel, eller om paketet
inte når fram.
I fortsättning kommer vi med begreppet ”error control”
eller ”felkontroll” att avse ARQ.
Protocols to be presented
•
•
•
•
Stop-and-wait ARQ
Sliding Window Flow Control
Go-back-N ARQ
Selective Repeat ARQ
Sliding Window
Protocols
The Stop-and-Wait Protocol
The simplest protocol for error and flow control
How the protocol operates:
○ Source may not send a new frame until the receiver acknowledges
previous one.
○ The receiver sends only positive acknowledgements (ACK) to notify
the sender that the frame was received.
○ If the frame 0 was received, the ACK 1 is sent. In that way the sender
is notified that the receiver is expecting frame 1.
○ The ID of the frame is called a sequence number.
○ 1 bit sequence numbers is sufficient. Sequence: 0 1 0 1 0 ... .
11.1
Normal operation
ACK n = Acknowledgement. Expecting frame number n
11.2
Stop-and-Wait ARQ, lost frame
Lost or Damaged Frame
• The sender starts a timer when it sends each frame
• If the ACK is not received before the timer expires, the
sender resends the same frame again
11.3
Stop-and-Wait ARQ, lost ACK frame
Lost or damaged ACK
• Lost ACK causes duplicate frames
• A duplicate frame is recognized by the sequence number
and is discarded
• The receiver sends the same ACK again
11.4
Stop-and-Wait ARQ, delayed ACK
Note:
Numbered acknowledgments are
needed if an acknowledgment is
delayed and the next frame is lost.
Piggybacking
• Usually the communication is in both ways – this means that
the sender is a receiver and the receiver is the sender, too.
(both send and receive data)
• To save on the processing and bandwidth the short ACKs
messages are not sent as separate frames. Instead, they may be
included in the frames with data.
• This technique is called piggybacking
11.5
Piggybacking
Efficiency of Stop-and-Wait
• Very inefficient, having in mind that most of the time the sender is idle
• Example: 40 km copper cable, 10 Mbps rate, 1000 bit frame,
○ Signal in copper propagates at 2 x 108 m/sec
○ Transmission time is 1000/10000000 (Takes 0.1 msec to transmit frame)
○ Propagation time is 40000/ 2 x 108 (0.2 msec delay to begin arriving at the
receiver)
○ Total time is 0.3 msec. to get to the receiver
○ ACK transmission time is approximately 0 (assuming the ACK is very short
(length  0)
○ 0.2 msec is the time for the ACK to arrive at the sender
• Total time is 0.5 msec before the sender can transmit again
• 0.5 ms for 0.1 msec frame or efficiency is 20%
Sliding-Window flow control
• Several frames can be sent without acknowledgement being received
• N is the window size – the maximum number of frames that can be sent
and not being acknowledged.
• The receiver must be able to buffer N frames.
• Sequence numbers are used to identify each frame. They are carried in the
header.
• The number of different sequence numbers must be at least N+1.
• If the field for sequence numbers allows m bits, the number of different
sequence number is 2m and the sequence numbers range from 0 to 2m-1.
In that case the maximum window size is N = 2m-1.
11.6 Sender sliding window
The sender window is the the set of frames that may be
transmitted before an ACK. It slides when the sender
has received an ACK and sent next frame.
11.7
Receiver sliding window
The receiver window is the the set of frames that may
be accepted before the buffer is full. While the buffer
is full, the receiver sends no ACK. The window of a
stuffed receiver slides when the receiver has
”consumed” a frame and thus sent an ACK.
Stop-and-Wait vs. Sliding Window
Window size N=3.
Sender
Sender
Receiver
Transmission +
propagation
Transmiss
time for the
ion time
packet
for the
packet
Transmission +
propagation
time for the
ACK
.
.
.
Sequence numbers are 1
bit long (0 or 1)
Frame
consumption
delay
Receiver
propagation
time
..
.
Frame
consumption
delay
...
Sequence numbers from 0 to 2m1. m-bit field for the seq. num.
Sender and Receiver Prospective
The window size
is 7
Sliding Window Flow Control
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
F0
F1
ACK1
F2
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
ACK2
F3
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
ACK3
F4
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
ACK4
F5
ACK5
ACK6
N=6
ARQ with Sliding Window
Problems arise when some of the frames are discarded (errors or lost
frames). Two strategies are developed to deal with this problem:
• Go-back-N strategy
○ The reciever simply discards all frames after the damaged frame without
sending acknowledgement.
• Selective repeat strategy
○ The receiver keeps all the frames after the damaged frame. It sends negative
acknowledgement (NACK) for the damaged frame. When the sender finaly
notice that something is wrong it retransmits the bad frame.
The two strategies are trade-offs between bandwidth and data-link buffer
space.
Go-Back-N Strategy
• If a frame is lost, the lost frame and all the frames sent after it are
sent again.
• Sending window of size N, receiving window of size 1.
• The sender has to buffer N frames
• Bandwidth is wasted.
11.9
Go-Back-N ARQ, normal operation
11.10
Go-Back-N ARQ, lost frame
11.11 Go-Back-N ARQ: sender window size
Selective Repeat Strategy
• Only retransmit the frames that are in error
• Both sending and receiving window are of size N
11.13
Selective Repeat ARQ, lost frame
11.14
Selective Repeat ARQ, sender window size
Bandwidth – Delay Product
• The product of the bit rate (bandwidth expressed as bits per
seconds) and the propagation time gives the number of bits
that can be on the channel and thus can give orientation
about the window size
• When propagation time is high (for example in satellite
channels), the window size need to be larger
Example 1
In a Stop-and-Wait ARQ system, the bandwidth of the line is 1 Mbps, and 1 bit
takes 20 ms to make a round trip. What is the bandwidth-delay product? If the
system data frames are 1000 bits in length, what is the utilization percentage of
the link?
Solution
The bandwidth-delay product is
1  106  20  10-3 = 20,000 bits
The system can send 20,000 bits during the time it takes for the data to go
from the sender to the receiver and then back again. However, the system
sends only 1000 bits. We can say that the link utilization is only 1000/20,000,
or 5%. For this reason, for a link with high bandwidth or long delay, use of
Stop-and-Wait ARQ wastes the capacity of the link.
Example 2
What is the utilization percentage of the link in Example 1 if the link uses GoBack-N ARQ with a 15-frame sequence?
Solution
The bandwidth-delay product is still 20,000. The system can send up to 15
frames or 15,000 bits during a round trip. This means the utilization is
15,000/20,000, or 75 percent. Of course, if there are damaged frames, the
utilization percentage is much less because frames have to be resent.
High-level Data Link Control
Protocol
• HDLC is one of the first protocols that implements mechanisms of
ARQ
• Supports half-duplex and full-duplex mode on point-to-point links
• Uses three types of frames: information (I-frames), supervisory (Sframes) and unnumbered (U-frames)
• Only I frames carry information, S frames carry transport control
information and U frames are used for managing the link
HDLC Frame Structure
Flag
Address
Control
• Flag: 01111110, at start and end
• Physical Address: secondary
station (for multidrop
configurations)
• Information: the data to be
transmitted
• Frame check sequence (FCS):
16- or 32-bit CRC
Information
FCS
Flag
• Control: purpose or function of
frame
○ Information frames: contain
user data
○ Supervisory frames: flow/error
control (ACK/ARQ)
○ Unnumbered frames: variety of
control functions (see p.220)
11.18
HDLC frame types
The Need for Bit Stuffing
• The flags show the receiver the start and the end of frame
• There is a problem if the flag appears in the middle of the
frame as a part of data
• The receiver will ”think” it is the end of frame
• A technique called “bit stuffing” is used to resolve this
problem
Bit Stuffing
• The sender stuffs redundant 0s
○ Every time it encounters five 1s in a row, it inserts a redundant 0
○ The redundant 0 tells the receiver that the sequence is not a flag
○ The receiver removes all redundant 0s to restore the original frame
○ Example: Bit stuff the following data:
0001111111110111100011111011
000111110111101111000111110011
Redundant 0s
11.24
Bit stuffing and removal
11.25
Bit stuffing in HDLC
PPP (Point-to-Point Protocol)
• Based upon HDLC
• Used for point-to-point access
• Common protocol used for connecting home users to the Internet (via
dial-up, DSL or cable modem or leased line)
• Defines the negotiation for establishment of the link
• Defines the protocol carried on the network layer
• Includes authentication and a field about the type of network protocol
carried within the frame
PPP Frame Format
Number of bytes in a field
1
1
Flag
Address
01111110 11111111
1
Control
00000011
1 or 2
variable
Protocol
Payload
2 or 4
CRC
1
Flag
01111110
 Physical Address field with all 1s indicate
broadcasting, i.e. that all stations accept the
frame
 Since the Address and Control fields are
constant, the two parties can negotiate to omit
them, thus saving 2 bytes
 Protocol field defines what is carried in the
payload field (user data or other information)
 CRC bits are error control bits
PART V
Transport Layer
Figure 22.1 Types of data deliveries
The transport layer is responsible for
process-to-process delivery.
Figure 22.9
Error control
Figure 22.2
Port numbers
Figure 22.3
IP addresses versus port numbers
Table 22.1 Well-known ports used by UDP
Port
Protocol
Description
7
Echo
Echoes a received datagram back to the sender
9
Discard
11
Users
13
Daytime
17
Quote
19
Chargen
53
Nameserver
67
Bootps
Server port to download bootstrap information
68
Bootpc
Client port to download bootstrap information
69
TFTP
Trivial File Transfer Protocol
111
RPC
Remote Procedure Call
123
NTP
Network Time Protocol
161
SNMP
Simple Network Management Protocol
162
SNMP
Simple Network Management Protocol (trap)
Discards any datagram that is received
Active users
Returns the date and the time
Returns a quote of the day
Returns a string of characters
Domain Name Service
Table 22.2 Well-known ports used by TCP
Port
Protocol
Description
7
Echo
Echoes a received datagram back to the sender
9
Discard
11
Users
13
Daytime
17
Quote
19
Chargen
20
FTP, Data
21
FTP, Control
23
TELNET
25
SMTP
53
DNS
67
BOOTP
79
Finger
Finger
80
HTTP
Hypertext Transfer Protocol
111
RPC
Discards any datagram that is received
Active users
Returns the date and the time
Returns a quote of the day
Returns a string of characters
File Transfer Protocol (data connection)
File Transfer Protocol (control connection)
Terminal Network
Simple Mail Transfer Protocol
Domain Name Server
Bootstrap Protocol
Remote Procedure Call
Note:
UDP is a connectionless, unreliable
protocol that has no flow and error
control. It uses port numbers to
multiplex data from the application
layer.
Figure 22.10
User datagram format
Note:
The calculation of checksum and its
inclusion in the user datagram are
optional.
Figure 22.11 Stream delivery
TCP offers stream delivery
– virtual circuit connection
over a packet oriented network
Note:
UDP is a convenient transport-layer
protocol for applications that provide
flow and error control. It is also used
by multimedia applications.
Figure 22.11 Stream delivery
Figure 22.12
Sending and receiving buffers
Figure 22.13 TCP segments
Example 1
Imagine a TCP connection is transferring a file of 6000 bytes. The
first byte is numbered 10010. What are the sequence numbers for
each segment if data are sent in five segments with the first four
segments carrying 1000 bytes and the last segment carrying 2000
bytes?
Solution
The following shows
Segment 1 ==>
Segment 2 ==>
Segment 3 ==>
Segment 4 ==>
Segment 5 ==>
the sequence number for each segment:
sequence number: 10,010 (range: 10,010
sequence number: 11,010 (range: 11,010
sequence number: 12,010 (range: 12,010
sequence number: 13,010 (range: 13,010
sequence number: 14,010 (range: 14,010
to 11,009)
to 12,009)
to 13,009)
to 14,009)
to 16,009)
Note:
The bytes of data being transferred in
each connection are numbered by
TCP. The numbering starts with a
randomly generated number.
Note:
The value of the sequence number
field in a segment defines the number
of the first data byte contained in that
segment.
Note:
The value of the acknowledgment field
in a segment defines the number of the
next byte a party expects to receive.
The acknowledgment number is
cumulative.
Figure 22.14 TCP segment format
Figure 22.15
Control field
Table 22.3 Description of flags in the control field
Flag
Description
URG
The value of the urgent pointer field is valid.
ACK
The value of the acknowledgment field is valid.
PSH
Push the data.
RST
The connection must be reset.
SYN
Synchronize sequence numbers during connection.
FIN
Terminate the connection.
Figure 22.16 Three-step connection establishment
Figure 22.17
Four-step connection termination
Table 22.4 States for TCP
State
Description
CLOSED
There is no connection.
LISTEN
The server is waiting for calls from the client.
SYN-SENT
A connection request is sent; waiting for acknowledgment.
SYN-RCVD
A connection request is received.
ESTABLISHED
Connection is established.
FIN-WAIT-1
The application has requested the closing of the connection.
FIN-WAIT-2
The other side has accepted the closing of the connection.
TIME-WAIT
Waiting for retransmitted segments to die.
CLOSE-WAIT
The server is waiting for the application to close.
LAST-ACK
The server is waiting for the last acknowledgment.
Figure 22.18
State transition diagram
Note:
A sliding window is used to make
transmission more efficient as well as
to control the flow of data so that the
destination does not become
overwhelmed with data. TCP’s sliding
windows are byte-oriented.
Figure 22.19
Sender buffer
Figure 22.20
Receiver window
Figure 22.21
Sender buffer and sender window
Figure 22.22
Sliding the sender window
Figure 22.23
Expanding the sender window
Figure 22.24
Shrinking the sender window
Note:
In TCP, the sender window size is
totally controlled by the receiver
window value (the number of empty
locations in the receiver buffer).
However, the actual window size can
be smaller if there is congestion in the
network.
Note:
Some points about TCP’s sliding windows:
The source does not have to send a full
window’s worth of data.
The size of the window can be increased or
decreased by the destination.
The destination can send an acknowledgment
at any time.
Figure 22.25
Lost segment
Figure 22.26
Lost acknowledgment
Figure 22.7
Connection establishment
Figure 22.8
Connection termination
Figure 22.27 TCP timers