high speed broadband communicationChapter11.ppt

fdj

1. Chapter 11 Link-Level Flow and Error Control
1
Chapter 11
Link-Level Flow and Error
Control

2. Chapter 11 Link-Level Flow and Error Control
2
Introduction
The need for flow and error control
Link control mechanisms
Performance of ARQ (Automatic Repeat
Request)

3. Chapter 11 Link-Level Flow and Error Control
3
Flow Control and Error Control
Fundamental mechanisms that determine
performance
Can be implemented at different levels:
link, network, or application
Difficult to model performance
Simplest case: point-to-point link
–Constant propagation
–Constant data rate
–Probabilistic error rate
–Traffic characteristics

4. Chapter 11 Link-Level Flow and Error Control
4
Flow Control
Limits the amount or rate of data that is
sent
Reasons:
–Source may send PDUs faster than destination
can process headers
–Higher-level protocol user at destination may
be slow in retrieving data
–Destination may need to limit incoming flow
to match outgoing flow for retransmission

5. Chapter 11 Link-Level Flow and Error Control
5
Flow Control at Multiple Protocol
Layers
X.25 virtual circuits (level 3) multiplexed
over a data link using LAPB (X.25 level 2)
Multiple TCP connections over HDLC link
Flow control at higher level applied to
each logical connection independently
Flow control at lower level applied to total
traffic

6. Chapter 11 Link-Level Flow and Error Control
6
Figure 11.1

7. Chapter 11 Link-Level Flow and Error Control
7
Flow Control Scope
Hop Scope
–Between intermediate systems that are directly
connected
Network interface
–Between end system and network
Entry-to-exit
–Between entry to network and exit from network
End-to-end
–Between end user systems

8. Chapter 11 Link-Level Flow and Error Control
8
Figure 11.2

9. Chapter 11 Link-Level Flow and Error Control
9
Error Control
Used to recover lost or damaged PDUs
Involves error detection and PDU
retransmission
Implemented together with flow control in
a single mechanism
Performed at various protocol levels

10. Chapter 11 Link-Level Flow and Error Control
10
Link Control Mechanisms
3 techniques at link level:
Stop-and-wait
Go-back-N
Selective-reject
Latter 2 are special cases of sliding-window
Assume 2 end systems connected by direct link

11. Chapter 11 Link-Level Flow and Error Control
11
Sequence of Frames
Source breaks up message into sequence of
frames
Buffer size of receiver may be limited
Longer transmission are more likely to
have an error
On a shared medium, avoids one station
monopolizing medium

12. Chapter 11 Link-Level Flow and Error Control
12
Stop and Wait
Source transmits frame
After reception, destination indicates
willingness to accept another frame in
acknowledgement
Source must wait for acknowledgement
before sending another frame
2 kinds of errors:
–Damaged frame at destination
–Damaged acknowledgement at source

13. Chapter 11 Link-Level Flow and Error Control
13
ARQ
Automatic Repeat Request
Uses:
–Error detection
–Timers
–Acknowledgements
–Retransmissions

14. Chapter 11 Link-Level Flow and Error Control
14
Figure 11.3

15. Chapter 11 Link-Level Flow and Error Control
15
Figure 11.4

16. Chapter 11 Link-Level Flow and Error Control
16
Stop-and-Wait Link Utilization
If T
prop large relative to T
framethen
throughput reduced
If propagation delay is long relative to
transmission time, line is mostly idle
Problem is only one frame in transit at a
time
Stop-and-Wait rarely used because of
inefficiency

17. Chapter 11 Link-Level Flow and Error Control
17
Sliding Window Techniques
Allow multiple frames to be in transit at
the same time
Source can send n frames without waiting
for acknowledgements
Destination can accept nframes
Destination acknowledges a frame by
sending acknowledgement with sequence
number of next frame expected (and
implicitly ready for next nframes)

18. Chapter 11 Link-Level Flow and Error Control
18
Figure 11.5

19. Chapter 11 Link-Level Flow and Error Control
19
Figure 11.6

20. Chapter 11 Link-Level Flow and Error Control
20
Go-back-N ARQ
Most common form of error control based on
sliding window
Number of un-acknowledged frames determined
by window size
Upon receiving a frame in error, destination
discards that frame and all subsequent frames
until damaged frame received correctly
Sender resends frame (and all subsequent frames)
either when it receives a Reject message or timer
expires

21. Chapter 11 Link-Level Flow and Error Control
21
Figure 11.7

22. Chapter 11 Link-Level Flow and Error Control
22
Figure 11.8

23. Chapter 11 Link-Level Flow and Error Control
23
Error-Free Stop and Wait
T = T
frame+ T
prop + T
proc + T
ack + T
prop + T
proc
T
frame = time to transmit frame
T
prop = propagation time
T
proc = processing time at station
T
ack = time to transmit ack
Assume T
proc andT
ackrelatively small

24. Chapter 11 Link-Level Flow and Error Control
24
T ≈ T
frame+ 2T
prop
Throughput = 1/T = 1/(T
frame+ 2T
prop) frames/sec
Normalize by link data rate: 1/ T
frameframes/sec
S = 1/(T
frame+ 2T
prop) = T
frame = 1
1/ T
frame T
frame+ 2T
prop 1 + 2a
where a = T
prop / T
frame

25. Chapter 11 Link-Level Flow and Error Control
25
Stop-and-Wait ARQ with Errors
P = probability a single frame is in error
N
x= 1
1 -P
= average number of times each frame must be
transmitted due to errors
S = 1 = 1 -P
N
x(1 + 2a) N
x(1 + 2a)

26. Chapter 11 Link-Level Flow and Error Control
26
The Parameter a
a = propagation time = d/V = Rd
transmission time L/R VL
where
d = distance between stations
V = velocity of signal propagation
L = length of frame in bits
R = data rate on link in bits per sec

27. Chapter 11 Link-Level Flow and Error Control
27
Table 11.1

28. Chapter 11 Link-Level Flow and Error Control
28
Figure 11.9

29. Chapter 11 Link-Level Flow and Error Control
29
Error-Free Sliding Window ARQ
Case 1: W ≥ 2a + 1
Ack for frame 1 reaches A before A has
exhausted its window
Case 2: W < 2a +1
A exhausts its window at t = W and cannot send
additional frames until t = 2a + 1

30. Chapter 11 Link-Level Flow and Error Control
30
Figure 11.10

31. Chapter 11 Link-Level Flow and Error Control
31
Normalized Throughput
1 W ≥ 2a + 1
S =
W W < 2a +1
2a + 1

32. Chapter 11 Link-Level Flow and Error Control
32
Selective Reject ARQ
1 -P W ≥ 2a + 1
S =
W(1 -P) W < 2a +1
2a + 1

33. Chapter 11 Link-Level Flow and Error Control
33
Go-Back-N ARQ
1 -P W ≥ 2a + 1
S = 1 + 2aP
W(1 -P) W < 2a +1
(2a + 1)(1 –P + WP)

34. Chapter 11 Link-Level Flow and Error Control
34
Figure 11.11

35. Chapter 11 Link-Level Flow and Error Control
35
Figure 11.12

36. Chapter 11 Link-Level Flow and Error Control
36
Figure 11.13

37. Chapter 11 Link-Level Flow and Error Control
37
High-Level Data Link Control
HDLC is the most important data link
control protocol
Widely used which forms basis of other
data link control protocols

38. Chapter 11 Link-Level Flow and Error Control
38
Figure 11.15

39. Chapter 11 Link-Level Flow and Error Control
39
HDLC Operation
Initialization
Data transfer
Disconnect

40. Chapter 11 Link-Level Flow and Error Control
40
Figure 11.16