# Flow Control, Error Control and Ethernet Frame Format

Introduction to flow control, Stop and Wait, GBN, Selective repeat, Error Control (CRC), Ethernet Frame Format: Header.

Content:
Content covered:

Stop & Wait, Go Back N and Selective repeat

## Responses

I read somewhere that GBN supports both cumulative and individual ack. Am I wrong??

GBN supports cumulative acknowledgemet(not exactly cumulative but cumulative with some modification)

Whenever receiver receive a packet a timer called acknowledgement timer(At receiver side) start and expire. By the time it expire how many ever packet are received in that gap going to send 1 acknowledgement

Time out timer(at sender side)>Ack timer(at receiver side

And Ack timer is not too big or not too small.

ya..i agree...SO we can say na that it supports both.

Yes GBN supprts both cumulative as well as Independent Acknowledgement. GBN with independent ACK is different than Stop & Wait protocol as in case of GBN(Even for individual ACK) We use the concept of pipelining. Only different in case of cumulative ACK is that it creates less traffic.

GBN always uses cummulative acknowledgement...

But if the ACK timer is too small then it would have to send a ack for each packet....

so, it uses cummulative ack only but may behave as independent if ACK timer is too small.

Check this for further clarification...

https://youtu.be/ZLtkhsgQp8U?list=PLEbnTDJUr_IegfoqO4iPnPYQui46QqT0j&t=1416

Pls correct if i am wrong...

Example on Example on Sliding Window Protocol

## Responses

I have one doubt in the above formula.The size of sender window is 1+2a or just 2a ??

It is 1+2a and my answer is also 41 according to formula.

If we will consider transmission dealy in RTT,then  maximum window size= 1+2a.
Otherwise according to the definition, RTT= 2*Propagation delay.
So both 40 and 41 are the possible answer.

In the example of video it is asked for optimal window size that means maximum windows size a sender can have..

as we know that ws+wr<=asn

here ws=sender window size

and asn = available sequence number = 1+2*(tp/tt)

actually RTT is 2*Propagation delay only, what has been missed in the video is the packet whose RTT is considered.

I mean initially a packet is sent and in the time we receive the ack for that, i.e., RTT, we utilize that time in sending more packets. The 'w' calculated in the video is the no. of packets sent in that time.

then we should add 1 for the packet already sent.. hence 40 + 1 = 41 is the window size.

Sir, pls confirm or correct....

GATE 2003
Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The send and receive window sizes are 5   packets each. Data packets (sent only from A to B) are all 1000 bits long and the transmission time for such a packet is 50 microsec Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200 microsec. What is the maximum achievable throughput in this communication?
(A) 7.69 × 106 bps (B) 11.11 × 106 bps
(C) 12.33 × 106 bps (D) 15.00 × 106 bp
• Explanation

Please first try yourself this question and then look at the answer and explanation.

First , please write down the data and convert it into simplest unit possible. it eliminates calculation mistakes and give always uniform answer ,which you can convert later in required quantity.

My personal approach in to convert

1)  bandwidth from mbps , gbps etc to bps,

2) Data size ( ack or frame) from bytes to bits ,

3)  time ( PT,Transmission time, RTT etc ) from Microsec , millisec to sec.

Sliding window protocol, Window size  W = 5, frame size  F = 1000 bits , F/C  that is transmission time of frame over link of capacity/bandwidth C = 50 * $10^{-6}$sec , ack A = 0 bits ( given negligible) ,  PT = 200*$10^{-6}$sec.

we dont have bandwidth C, but we can find out it by using Transmission time TT= 50 *$10^{-6}$sec

F/C= 50* $10^{-6}$ sec=>  1000 bits/C= 50* $10^{-6}$sec => C = 1000 / 50 * $10^{-6}$ bps = 20 * $10^6$ bps => C = 20mbps

Efficiency of anything is defined as useful time out of total time.

Useful time will be transmission time TT of the frame which is 50 microsec * Window size = 50 * 5 * $10^{-6}$sec

total time will be transmission time + RTT + Ack transmission time, not W *TT + RTT+ A/C. A/C is 0 as A = 0.

In sliding window protocol, the transmission of 2nd and subsequent frames can be overlapped with propagation time of 1st frame and so on. so total time does not include  Window size * transmission time. Rather it  is just transmission of 1st frame and thats it.

So efficiency of the protocol will be => TT/ ( TT+RTT+A/C) => TT / TT + RTT => 5*50 *$10^{-6}$sec /( 50*$10^{-6}$+ 2*200*$10^{-6}$) sec => 250/(50+400) => 250 /450 => 0.5555 => 55.55 %

Throughput = Efficiency of link * bandwidth = 0.5555* 20 * $10^6$ bps => 11.11.*$10^6$ bps.

answer : 11.11 * $10^6$bps.

## Responses

Not Understood can anyone explain with all the terms used in detail??

The channel is full duplex so shouldn't RTT be PT reather than 2*PT??

but full duplex means that u can send and recieve at same time. the bandwidth of channel is shared

here, the packet first need to be received by the receiver then only it can send Ack. Both actions can't happen simultaneously.

so it is always 2*PT

RTT is always 2*PT.

Sliding Window uses full duplex only.

$ɑ = { Propagation delay (Tp)\over Transmission delay (Tt)}$

 Stop & Wait GBN SR Efficiency ${1 \over1+ 2a}$ ${N \over 1+2a}$ ${N \over 1+2a}$ Sequence Numbers (1+1) (N+1) (N+N) Retransmissions (for 1 packet lost ) 1 N 1 Buffers (1+1) (N+1) (N+N) Bandwidth Low High Medium CPU Low Medium High Implementation Low Medium High

In CSMA/CD, minimum length of packet to detect collision, L >= 2 * Tp * Bandwidth
Ethernet Frame Format (IEEE 802.3):

(Img.Source- cse.iitk.ac.in/users/dheeraj/cs425/lec06.html/)

After some transmission on Ethernet, current frame of A's is collided 2 times and B's is collided 4 times. The probability that A wins the present back off race is____.

• Explanation

Number of times A has been involved in collision = 2
Number of times B has been involved in collision = 4
A can choose any number between (0 to 22-1 ) , i.e, (0,1,2,3)
B can choose any number between (0 to 24-1 ) , i.e, (0,1,2,3,......,15)
It is given that A wins the race, so choices for (A,B) will be:
(0,1) , (0,2) ,(0,3)................ , (0,15)
(1,2), (1,3),...........................,(1,15)
(2,3),(2,4),............................,(2,15)
(3,4),(3,5),.............................,(3,15)
Total choices = 15 + 14 + 13 + 12 = 54 out of 64 choices.

So probability = 54 / 64 = 0.84

## Responses

Because that's what <b>it</b> means!

What is probability of collisons? is it 4/64.

Yes!
1 Collision: (0,0)(1,1)(2,2)(3,3) {4/64}.
2 B wins the race: (1,0)(2,0)(3,0)(2,1)(3,1)(3,2) {6/64}

I think the ans given in this question is of B's winning the race which is 54/64

For A's winning the race it is 6/64......

and for collision it is 4/64....

Correct me If I'm wrong......:-)

For collision both A and B's waiting time must be equal  (0,0) (1,1) (2,2) (3,3)      - only 4 possibilities out of 64              for collision

For  B to win it has to transmit before A (1,0) (2,0) (2,1) (3,0) (3,1) (3,2)   -    only 6 possibilities out of 64                           for B to win the race.

In remaining all cases, A will have lesser waiting time than B  so A will win the race  in  -  54 possibilities out of 64 .       for A to win the race.

Consider SWP with error probability 0.2. Suppose if sender wants to send 800 packets then how many packets have to be transmitted in total ?

• Explanation

Assume error probability is 'p' and number of  packets that we want to send are 'n'.
So total transmission needed will be :
n+n*p + n*p*p + n*p*p*p.......
= n(1+p + p2 + p3 +..... )
= n(1/1-p)
Here n=800 and p =0.2
So no. of transmissions = 800* (1/(1-0.2)
=800 * (1/0.8)
=1000
Hence total 1000 tranmission will take place.

## Responses

What if we approach the question like this - Out of every 5 packets one has to be resent again(ie. error).

Then for 800 packets - 160 sent again

for 160 packets - 32 sent again

for 32 packets - 6 sent again

for 6 packets - 1 sent again

Then total packets sent = 800+160+32+1=999

Where am I missing something ?

I think you have missed a decimal points

for 32 packets - 6.4 sent again

for 6.4 packets -1.28 sent again

Then total packets sent=800+160+32+6.4+1.28=1000

I am not sure.

If i am wrong then correct me

why we have done n+n*p+n*p*p.....?

As error probability is 0.2 i.e In 100 packets 20 will be going to lost.
Here, for 800 packets, 160 packets will be going to lost. Then, we have to send these 160 packets with the same protocol again. Again in 160 packets, we will be going to lost 0.2 of 160.
Thus we are getting a series like 800+800x0.2+160x0.2..... = 800+800(0.2)+800(0.2)(0.2)+.....
i.e n+np+np2+.... = n(1+p+p2+p3+...) which is a gp and formula is  n(1/1-p). where n =800, p= 0.2
Using, this formula we can get the answer directly.

In GB4, if every 6th packet being transmitted is lost and if we have to send 10 packets, then how many transmissions are required?

## Responses

can anyone explain it?

Sir, in intro video, you said sender's window size is n-1 in GBN, here you are taking 4 in GB4.

no its not like this..if u have GB4 means ur sender window size is 4...and ur recievers window is always 1 in GBN...
sir must have meant that if u have n sequence nos then u can give n-1 to sender and 1 different to reciever to avoid duplicate packets...

sir do u have any formule to calculate the above types problems?

Determine the maximum length of the cable (in km) for transmitting data at a rate of 500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal speed in the cable to be 2,00,000 km/s.

• Explanation

Tt >=2*Tp
L(length of the cable)<=(Data size*Signal speed)/(2*Bandwidth)
L<=(10,000 bits * 2 *108m/s)/(2*500*106b/s)
L<=2000m
Hence L<=2Km.

## Responses

Can someone explain second step

Tt>=2*Tp

Tt =Length of data/Bandwidth

Tp =Distance/Velocity

just substitute the value in the eqn in line 1.

Can someone explain second step

in secon step we used the formula for transmission time which is length of frame(or packet)/bandwidth and the formula for propagation delay which is distance to be covered (the length of our channel or cable)/ speed of the signal. On rearranging these terms we get the second step.

• This quiz contains 5 questions on the topic Data Link Layer
• Lean well before you attempt the quiz
• You can attempt the quiz unlimited number of times.

Difficulty Level:  basic
No. of Questions:  5

Awesome, you did good to complete todays course.

## Responses

where is the quiz sir?

Quiz is live now.

pls paste the link of quiz. i am not able to see the quiz link on this topic.

Now you can see.

Now you can attempt the quiz.

I can't see Quiz icon,why?

Now you can attempt the quiz.

Where we can find quiz solutions?

Can you please share the solutions for the quiz

nyc quiz ... good work

Can someone clear doubt regarding 2D parity as written in NPTEL slides that 2D parity can detect a burst error of n bits and >n+1 bits is detected but probabilty is less compared to n bits?

According to me, 1bit errors can be corrected and detected

2 bit errors can't be corrected and detected.

There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that ONLY one station transmits in a given time slot?

How is this np(1-p)^(n-1)?? pls explain...

@dashish

probability that only one station transmits in a given slot = probability that one station transmit * probability that others don't transmit.

probability that only one station transmits in a given slot = p.

probability that others don't transmit =(1-p)(n-1).

for n stations required probability =n*( p * (1-p)(n-1)).

n is multiplied because we can choose the transmitting station in nC1 ways.

hope it helps.

@amit0368

Thanks! I missed the point u made bold......