Data Communication and Computer Networks

FLOW CONTROL

• Flow control is a technique for assuring that a transmitting entity does

not overwhelm a receiving entity with data.

110110101

• The data are sent in a sequence of frames.

• Each frame contains a portion of the data and some control information.

.
FLOW CONTROL

• Receiving entity typically allocates a data buffer of some maximum length for a
transfer.

• In the absence of flow control, the receiver’s buffer may fill up and overflow
while it is processing old data.

.
FLOW CONTROL
• Mechanisms for flow control in the absence of errors.

• Figure shows vertical-time sequence diagram.

Figure 7.1 Model of Frame Transmission

.
FLOW CONTROL

• Transmission time : Time it taken for a station to emit all of the bits of
a frame onto the medium.

• Propagation time : Time taken for a bit to traverse the link between
source and destination.

.
FLOW CONTROL

assumption

• All frames that are transmitted are successfully received.

• Frames arrive in the same order in which they are sent.

• However, each transmitted frame suffers an arbitrary and variable

amount of delay before reception.

.
 Stop-and-Wait Flow Control

• A source entity transmits a frame.

• The source must wait until it receives the acknowledgment before sending the
next frame.
• Destination can thus stop the flow of data simply by with holding
acknowledgment.

.
Sliding-Window Flow Control

• The problem with stop and wait is that only one frame at a time can
be in transit.

• For very high data rates, for very long distances between sender and
receiver, stop-and-wait flow control provides inefficient line utilization.

• Efficiency can be greatly improved by allowing multiple frames to be

in transit at the same time.

.
Sliding-Window Flow Control

• Consider two stations A and B.

• Station B allocates buffer space for W frames.

• Thus, B can accept W frames, and A is allowed to send W frames

without waiting for any acknowledgments.

.
Sliding-Window Flow Control

• To keep track of which frames have been acknowledged, each is labeled with
a sequence number.

• B acknowledges a frame by sending an acknowledgment that includes the

sequence number of the next frame expected.
.
Sliding-Window Flow Control

• This scheme can also be used to acknowledge multiple frames.

• B could receive frames 2, 3, and 4 but withhold acknowledgment until frame 4

has arrived.

• By then returning an acknowledgment with sequence number 5, B

acknowledges frames 2, 3, and 4 at one time.
.
Sliding-Window Flow Control

• Sender maintains a list of sequence numbers that it is allowed to send.

(sender window)

• Receiver maintains a list of sequence numbers that it is prepared to receive.

(Receiver window)

• Each of these lists can be thought of as a window of frames.

• The operation is referred to as sliding-window flow control.

.
Sliding-Window Flow Control

• Because the sequence number to be used occupies a field in the

frame, it is limited to a range of values.

• For a 3-bit field, the sequence number can range from 0 to 7.

• For a k-bit field the range of sequence numbers is 0 through

• The maximum window size is

.
 Sliding-Window Flow Control

• Assumes the use of a 3-bit sequence number

• The shaded rectangle indicates the frames that may be sent;

• Here window size is 5.

.
 Sliding-Window Flow Control

• Each time a frame is sent, the shaded window shrinks;

• each time an acknowledgment is received, the shaded window grows.

• Frames between vertical bar and the shaded window have been sent but not yet
acknowledged. Sender must buffer these frames in case they need to be retransmitted.

.
Sliding-Window Flow Control

.
Flow Control

.
 Sliding-Window Flow Control

• Example assumes a 3-bit sequence number field and a maximum window size of seven
frames.

.
Sliding-Window Flow Control

• Receive Not Ready (RNR) message acknowledges former frames but forbids
transfer of future frames.

• RNR 5 means “received all frames up to number 4 but unable to accept any
more at this time.”

• At some subsequent point, the station must send a normal acknowledgment to

reopen the window.

.
Sliding-Window Flow Control

• So far discussed : transmission in one direction only.

• If two stations exchange data, each needs to maintain two windows, one for
transmit and one for receive.

• To provide efficient support for this requirement, a feature known as

piggybacking is typically provided.

• Each data frame includes a field that holds the sequence number of that
frame plus a field that holds the sequence number used for acknowledgment.

.
Sliding-Window Flow Control

• if a station has data and acknowledgment to send, it sends both together in

one frame.

• if a station has an acknowledgment but no data to send, it sends a separate

acknowledgment frame, such as RR or RNR.

• If a station has data to send but no acknowledgment to send, it must repeat

the last acknowledgment sequence number that it sent.

• This is because the data frame includes a field for the acknowledgment number,
and some value must be put into that field.

• When a station receives a duplicate acknowledgment, it simply ignores it.

.
ERROR CONTROL

• Error control refers to mechanisms to detect and correct errors that occur in
the transmission of frames.

Figure 7.1 Model of Frame Transmission

.
ERROR CONTROL

The possibility of two types of errors:

• Lost frame: A frame fails to arrive at the other side.

• Damaged frame: Some of the bits are in error.

.
 ERROR CONTROL

Most common techniques for error control are :

• Error detection: discussed.

• Positive acknowledgment: Destination returns a positive acknowledgment to

successfully received, error-free frames.

• Retransmission after timeout: Source retransmits a frame that has not been
acknowledged after a predetermined amount of time.

• Negative acknowledgment and retransmission: Destination returns a negative

acknowledgment to frames in which an error is detected. Source retransmits
such frames.

.
ERROR CONTROL

Collectively, these mechanisms are all referred to as automatic repeat request

(ARQ);

The effect of ARQ is to turn an unreliable data link into a reliable one.

Three versions of ARQ have been standardized:

• Stop-and-wait ARQ

• Go-back-N ARQ

• Selective-reject ARQ

All of these forms are based on the use of the flow control techniques.

.
 Stop-and-Wait ARQ

• Stop-and-wait ARQ is based on the stop-and-wait flow control technique.

 Source station transmits a single frame and then must await an

acknowledgment (ACK).

 No other data frames can be sent until the destination station’s reply
arrives.

.
Stop-and-Wait ARQ

• Two sorts of errors could occur.

• First, the frame that arrives at the destination could be damaged.

• Receiver detects this by error-detection technique & simply discards the frame.

• The source station is equipped with a timer.

• After a frame is transmitted, the source station waits for an acknowledgment.

• If no acknowledgment is received by the time that the timer expires, then the
same frame is sent again.

• Requires that the transmitter maintain a copy of a transmitted frame until an

acknowledgment is received for that frame.

.
Stop-and-Wait ARQ

• The second sort of error is a damaged acknowledgment.

• Station A sends a frame. Frame is received correctly by station B, which

responds with an acknowledgment (ACK).

• ACK is damaged in transit and is not recognizable by A, which will therefore

time out and resend the same frame.

.
Stop-and-Wait ARQ

• This duplicate frame arrives and is accepted by B.

• B has therefore accepted two copies of the same frame as if they were
separate.

• To avoid this problem, frames are alternately labeled with 0 or 1, and positive
acknowledgments are of the form ACK0 and ACK1.

• ACK0 acknowledges receipt of a frame numbered 1 and indicates that the

receiver is ready for a frame numbered 0.

.
Stop-and-Wait ARQ

• Frame transmitted by A is lost or

damaged and therefore B does not return
an ACK.

• A times out and retransmits the frame.

Figure 7.5 Stop-and-Wait ARQ

.
Stop-and-Wait ARQ

• A transmits a frame labeled 1 but the

ACK0 for that frame is lost.

• A times out and retransmits the same

frame.

• When B receives two frames in a row

with the same label, it discards the
second frame but sends back an ACK0 to
each.

Figure 7.5 Stop-and-Wait ARQ

.
 Go-Back-N ARQ

• Based on sliding-window flow control that is most commonly used.

• Station send a series of frames sequentially numbered modulo some

maximum value.

.
Go-Back-N ARQ

no errors :

• Destination will acknowledge incoming frames ( or piggybacked

acknowledgment).

error

• send a negative acknowledgment for that frame.

• Destination station will discard that frame and all future incoming frames until
the frame in error is correctly received.

• Source station, when it receives a REJ, must retransmit the frame in error
plus all succeeding frames that were transmitted in the interim.

.
Go-Back-N ARQ

• Suppose that station A is sending frames to station B.

• After each transmission, A sets an acknowledgment timer for the frame just
transmitted.

• Suppose that B has previously successfully received frame (i – 1) and A has

just transmitted frame i.

• The go-back-N technique takes into account the following contingencies:

.
Go-Back-N ARQ
1. Damaged frame. If the received frame is invalid (i.e., B detects an error ), B
discards the frame. There are two subcases:

a) Within a reasonable period of time, A subsequently sends

frame ,B receives frame out of order and sends a
REJ i. A must retransmit frame i and all subsequent frames.

a) A does not soon send additional frames. B receives nothing and returns
neither an RR nor a REJ. When A’s timer expires, it transmits an RR
frame that includes a bit known as the P bit, which is set to 1. B interprets
the RR frame with a P bit of 1 as a command that must be acknowledged
by sending an RR indicating the next frame that it expects, which is frame
i. When A receives the RR, it retransmits frame i. Alternatively, A could
just retransmit frame i when its timer expires.

.
Go-Back-N ARQ

2. Damaged RR. There are two subcases:

a) B receives frame i and sends RR (i+1) which suffers an error in transit.

Because acknowledgments are cumulative (e.g., RR 6 means that all frames
through 5 are acknowledged), it may be that A will receive a subsequent RR
to a subsequent frame and that it will arrive before the timer associated with
frame i expires.

b) If A’s timer expires, it transmits an RR command as in Case 1b. It sets another

timer, called the P-bit timer. If B fails to respond to the RR command, or if its
response suffers an error in transit, then A’s P-bit timer will expire. At this
point, A will try again by issuing a new RR command and restarting the P-bit
timer. This procedure is tried for a number of iterations. If A fails to obtain an
acknowledgment after some maximum number of attempts, it initiates a reset
procedure.

3. Damaged REJ. If a REJ is lost, this is equivalent to Case 1b.

.
Go-Back-N ARQ

• Here, frame 4 is damaged.

• Frames 5 and 6 are received out of

order and are discarded by B.

• When frame 5 arrives, B immediately

sends a REJ 4.

• When the REJ to frame 4 is received,

not only frame 4 but frames 5 and 6
must be retransmitted.

.
Go-Back-N ARQ

• Figure 7.6a also shows an

example of retransmission after
timeout.

• No acknowledgment is received
for frame 5 within the timeout
period, so A issues an RR to
determine the status of B.

.
Go-Back-N ARQ
• For a k-bit sequence number field, which provides a sequence number range of the
maximum sender window size is limited to

• Receiver window size is 1.

.
Go-Back-N ARQ

• Assume a 3-bit sequence number (sequence number ).

• Suppose a station sends frame 0 and gets back an RR 1 and

then sends frames 1, 2, 3, 4, 5, 6, 7, 0 and gets another RR 1.

• This could mean that all eight frames were received correctly and the RR 1 is a
cumulative acknowledgment.

• It could also mean that all eight frames were damaged or lost in transit, and the
receiving station is repeating its previous RR 1.

• The problem is avoided if the maximum window size is limited to

.
 Selective-Reject ARQ

With selective-reject ARQ, the only frames

retransmitted are those that receive a negative
acknowledgment, in this case called SREJ, or those
that time out.

.
 Selective-Reject ARQ
• When frame 5 is received out of order, B sends a
SREJ 4, indicating that frame 4 has not been
received.

• B continues to accept incoming frames and buffers

them until a valid frame 4 is received.

• At that point, B can place the frames in the proper

order for delivery to higher-layer software.

.
Selective-Reject ARQ
• Selective reject would appear to be more efficient than go-back-N, because it
minimizes the amount of retransmission.

• On the other hand, the receiver :

– must maintain a buffer large enough to save post-SREJ frames until the
frame in error is retransmitted and
– must contain logic for reinserting that frame in the proper sequence.

• The transmitter, too,

– requires more complex logic to be able to send a frame out of sequence.

.
Selective-Reject ARQ
• Because of such complications, select-reject ARQ is much less widely used
than go-back-N ARQ.

• Selective reject is a useful choice for a satellite link because of the long
propagation delay involved.

.
Selective-Reject ARQ
Window size limitation is more restrictive for selective-reject than for goback-N.

.
Selective-Reject ARQ

Consider the case of a 3-bit sequence number.

Allow a window size of seven, and consider the following scenario:

1. Station A sends frames 0 through 6 to station B.

2. Station B receives all seven frames and cumulatively acknowledges with RR 7.

3. Assume the RR 7 is lost.

4. A times out and retransmits frame 0.

5. B has already advanced its receive window to accept frames 7, 0, 1, 2, 3, 4,

and 5. Thus it assumes that frame 7 has been lost and that this is a new frame
0, which it accepts.

.
Selective-Reject ARQ

• To overcome the problem, the maximum window size should be no more than
half the range of sequence numbers.

• In general, for a k-bit sequence number field, which provides a sequence

number range of 2k, the maximum window size is limited to 2k-1.

.
PERFORMANCE ISSUES
Stop-and-Wait Flow Control

Suppose that a long message is to be sent as a sequence of frames

F1,F2,…….Fn from S1 to S2

.
PERFORMANCE ISSUES
Stop-and-Wait Flow Control

Assumptions:
• Processing time is relatively negligible
• Acknowledgment frame is very small compared to a data frame.

Then we can express the total time to send the data as

.
PERFORMANCE ISSUES
Stop-and-Wait Flow Control

Of that time, only is actually spent transmitting data and the rest is
overhead.

The utilization, or efficiency, of the line is

Divide numerator and denominator by and substitute

.
PERFORMANCE ISSUES
Stop-and-Wait Flow Control

propagation time : distance d of the link divided by the velocity of propagation V.

propagation time =

For unguided transmission through air or V =

For guided transmission, V is approximately 0.67 times the speed of light

for optical fiber and copper media.

transmission time : length of the frame in bits, L, divided by the data rate R.

transmission time =

.
PERFORMANCE ISSUES
Error-Free Sliding-Window Flow Control

• To evaluate performance, we need to consider two cases:

Therefore, express the utilization as

.
PERFORMANCE ISSUES

1) A is source, B is destination. A and B are separated by

a distance of 48,000kms. A sends 1500 bytes to B at the
rate of 100 Mbps. The signal propagates at 2.4 x 10^8
mps. Compute the propagation delay and transmission
delay considering there is no other intermediate device.

.
PERFORMANCE ISSUES

.
Example 1
A system uses the Stop-and-Wait ARQ Protocol. If each frame carries 1000 bits
of data, how long does it take to send 1 million bits of data if the distance
between the sender and receiver is 5000 Km and the propagation speed is 2 x
108 m? Ignore transmission, waiting, and processing delays. Assume no data
or control frame is lost or damaged.

.
Example 1
A system uses the Stop-and-Wait ARQ Protocol. If each frame carries 1000 bits
of data, how long does it take to send 1 million bits of data if the distance
between the sender and receiver is 5000 Km and the propagation speed is 2 x
108 m? Ignore transmission, waiting, and processing delays. Assume no data
or control frame is lost or damaged.

Propagation delay=d/V
d=5000km=5 x 106 m, V= 2 x 108 m
Propagation delay=5 x 106 / 2 x 108 =25ms

Nr of frame=1000000/1000=1000
Time delay for one successful frame delivery is 50ms(25ms* 2)
For 1000 frame, time delay=1000x50ms=50s

.
Example 2

Consider the use of 1000-bit frames on a 1-Mbps satellite channel with a 270-ms
delay. What is the maximum link utilization for
a) Stop-and-wait flow control?
b) Continuous flow control with a window size of 7?
c) Continuous flow control with a window size of 127?
d) Continuous flow control with a window size of 255?

.
Example 2

Consider the use of 1000-bit frames on a 1-Mbps satellite channel with a 270-ms
delay. What is the maximum link utilization for
a) Stop-and-wait flow control?
b) Continuous flow control with a window size of 7?
c) Continuous flow control with a window size of 127?
d) Continuous flow control with a window size of 255?

a= propagation Time/(L/R)
a=270 ×10−3/(103/ 106) = 270
a)U = 1/(1 + 2a) = 1/541 = 0.002
b)U = W/(1 + 2a) = 7/541 = 0.013
c)U = 127/541 = 0.23
d)U = 255/541 = 0.47

.
Example 3

Using 5-bit sequence numbers, what is the maximum size of the

send and receive windows for each of the following protocols?
a. Stop-and-Wait ARQ
b. Go-Back-NARQ
c. Selective-Repeat ARQ

.
Example 3

Using 5-bit sequence numbers, what is the maximum size of the

send and receive windows for each of the following protocols?
a. Stop-and-Wait ARQ
b. Go-Back-NARQ
c. Selective-Repeat ARQ

a) Stop-and-Wait ARQ=20
b) Go-Back-NARQ=25 -1
c) Selective-Repeat ARQ=25-1

.
Example 4

A sender sends a series of frame to the same destination using 5-bit

sequence numbers. If the sequence number starts with 0, what is
the sequence number after sending 100 frame?

.
Example 4

A sender sends a series of frame to the same destination using 5-bit

sequence numbers. If the sequence number starts with 0, what is
the sequence number after sending 100 frame?

A five-bit sequence number can create sequence numbers from 0 to 31

The sequence number in the Nth frame is (N mod 32)
101th frame has the sequence number (101 mod 32) or 5.

.
Example 5

A system uses the Go-back-N ARQ Protocol with a window size of

7. If each frame carries 1000 bits of data, how long does it take to
send 1 million bits of data if the distance between the sender and
receiver is 5000 Km and the propagation speed is 2 x 108 m?

Ignore the overhead due to the header and trailer. (Assume transmission
time of frame=1ms)

.
Example 5

A system uses the Go-back-N ARQ Protocol with a window size of

7. If each frame carries 1000 bits of data, how long does it take to
send 1 million bits of data if the distance between the sender and
receiver is 5000 Km and the propagation speed is 2 x 108 m?

Ignore the overhead due to the header and trailer. (Assume transmission
time of frame=1ms)

We need to send w=7 frame

1000000/7000=143 windows
Transmission time of window =7x1ms=7ms
Delay for 1 window
=twframe+2tprop =7+50=57ms
Delay for 143 windows
=143x57ms=8.151s

.
Ethernet Frame Format
IEEE Standards

In 1985, the Computer Society of the IEEE started a project, called Project
802, to set standards to enable intercommunication among equipment from a
variety of manufacturers.

It is a way of specifying functions of the physical layer and the data link layer
of major LAN protocols.

world’s largest technical professional organization,

.
Ethernet Frame Format
IEEE Standards

In 1985, the Computer Society of the IEEE started a project, called Project
802, to set standards to enable intercommunication among equipment from a
variety of manufacturers.

It is a way of specifying functions of the physical layer and the data link layer
of major LAN protocols.

world’s largest technical professional organization,

.
Ethernet Frame Format

IEEE 802.3 is the standard for Ethernet — the most widely used technology for wired
Local Area Networks (LANs).

.
 Ethernet Frame Format

Preamble (7 bytes): 7 bytes (56 bits) of alternating 0s and 1s used to alert & synchronize
receiver, sender clock rates.

SFD (1 byte): Start Frame Delimiter, flag (10101011): Signals the beginning of the frame.
Last two bits 11 alert the receiver that the next field is the destination address.

Destination and source address: MAC address of source and destination.

Type/Length (2 Bytes): Length: Up to 1500 (max length)

Type: Identify higher-layer data(0x0800 –IPv4 , 0x0806-ARP)

CRC(Cyclic Redundancy Check 4 Bytes): checked at receiver, if error is detected, the

frame is simply dropped

Data: 46 to 1500 Bytes (if shorter: add pad)

.
 Access Control

When two or more nodes transmit at the same time, their frames will collide
and the link bandwidth is wasted during collision.

MAC protocol : to coordinate the transmission of the active nodes.

.
Multiple Access Protocols: Main task is to minimize collisions in order
to utilize the bandwidth by:

 Determining when a station can use the link (medium)

 what a station should do when the link is busy
 what the station should do when it is involved in collision

.
 CSMA/CD
IEEE 802.3 standard defines carrier sense multiple access with collision
detection (CSMA/CD) as the access method for traditional Ethernet.

CSMA method was developed to minimize the chance of collision .

Collision can be reduced if a station senses the medium before trying to use it.

CSMA requires that each station first listen to the medium before sending.

CSMA can reduce the possibility of collision, but it cannot eliminate it.

.
 CSMA/CD
The possibility of collision still exists because of propagation delay;

When a station sends a frame, it still takes time (although very short) for the first
bit to reach every station and for every station to sense it.

Station may sense the medium and find it idle, only because the first bit sent by
another station has not yet been received.

.
 CSMA/CD
Carrier sense multiple access with collision detection (CSMA/CD)
augments the algorithm to handle the collision.

In this method, a station monitors the medium after it sends a frame to

see if the transmission was successful.

If so, the station is finished. If, however, there is a collision, the frame is
sent again.

.
 In Figure, stations A and C are involved in the collision.

At time t1, station A has started sending the bits of its frame. At time t2, station C has not yet sensed
the first bit sent by A. Station C starts sending the bits in its frame, which propagate both to the left
and to the right.
The collision occurs sometime after time t2. Station C detects a collision at time t3 when it receives
the first bit of A’s frame. Station C immediately aborts transmission.
Station A detects collision at time t4 when it receives the first bit of C’s frame; it also immediately
aborts transmission.
A transmits for the duration t4- t1; C transmits for the duration t3- t2.

.
.
 Energy level during transmission, idleness, or collision

• level of energy in a channel can be: zero, normal, and abnormal.

• At the zero level, the channel is idle.

• Normal level : station has successfully captured the channel and is sending its frame.

• abnormal level : there is a collision and the level of the energy is twice the normal level.

• A station that has a frame to send or is sending a frame needs to monitor the energy level
to determine if the channel is idle, busy, or in collision mode.

.
 A P – ip address
10 95 mac address

.
end

.
HIGH-LEVEL DATA LINK CONTROL (HDLC)

Frame Structure

.
8.80
Purpose of Jamming Signal:
[Link] All Stations Detect the Collision
1. Collisions may only be sensed by stations near the transmitters.
2. Jamming signal makes the collision loud enough so every station on the network
knows a collision occurred.
[Link] Partial Transmission from Being Mistaken as Valid
1. Without jamming, some nodes might receive a very short corrupted frame and
mistakenly treat it as valid.
2. Jamming guarantees the corrupted frame is long enough to be invalid.
[Link] Retransmission Procedure (Backoff Algorithm)
1. After jamming, all nodes stop transmitting.
2. Each waits a random backoff time (using Binary Exponential Backoff) before
retrying, reducing the chance of repeated collisions.

.
.
.
.
.
 Tutorial

A system uses the Go-back-N ARQ Protocol with a window size of

7. If each frame carries 1000 bits of data, how long does it take to
send 1 million bits of data if the distance between the sender and
receiver is 5000 Km and the propagation speed is 2 x 108 m?

Ignore the overhead due to the header and trailer. (Assume transmission
time of frame=1ms)

.
Example 5

A system uses the Go-back-N ARQ Protocol with a window size of

7. If each frame carries 1000 bits of data, how long does it take to
send 1 million bits of data if the distance between the sender and
receiver is 5000 Km and the propagation speed is 2 x 108 m?

Ignore the overhead due to the header and trailer. (Assume transmission
time of frame=1ms)

We need to send w=7 frame

1000000/7000=143 windows
Transmission time of window =7x1ms=7ms
Delay for 1 window
=twframe+2tprop =7+50=57ms
Delay for 143 windows
=143x57ms=8.151s