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

?
##### Important points about Stop & Wait, Go Back N and Selective repeat
Content covered:

Stop & Wait, Go Back N and Selective repeat

More Less

Example on Example on Sliding Window Protocol

##### Host A is sending data to host B over a f : GATE 2003
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

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.

##### Flow Control and Ethernet Frame Format (IEEE 802.3)

$ɑ = { 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/)

##### Backoff Algorithm

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____.

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

##### SWP

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 ?

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.

##### GBN

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

So total 17 transmissions are required.

##### Ethernet

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.

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.

• 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.

#### To continue your preparation while we publish tomorrow’s topic,

Back to Course
ABHISEK DAS 28 Dec 2016 01:36 pm

where is the quiz sir?

Sumit Verma 28 Dec 2016 02:01 pm

Quiz is live now.

Mohit Chawla 28 Dec 2016 03:42 pm

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

Sumit Verma 28 Dec 2016 04:20 pm

Now you can see.

Sumit Verma 28 Dec 2016 04:21 pm

Now you can attempt the quiz.

Prajwal Bhat 28 Dec 2016 03:46 pm

I can't see Quiz icon,why?

Sumit Verma 28 Dec 2016 04:21 pm

Now you can attempt the quiz.

Parth Gadoya 31 Dec 2016 11:46 am

Where we can find quiz solutions?

Deepanshu Agrawal 1 Jan 2017 04:16 pm

Can you please share the solutions for the quiz

priyanka gautam 5 Jan 2017 01:22 pm

nyc quiz ... good work

Aditya Singh Bisht 7 Jan 2017 01:38 pm

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.

Ashish Kumar Goyal 21 Jan 2017 08:55 pm

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...

Amit Kumar 21 Jan 2017 09:57 pm

@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.

Ashish Kumar Goyal 22 Jan 2017 12:52 pm

@amit0368

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