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

luckysunda's picture

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

shraddhagami's picture

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.

luckysunda's picture

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

shiveshroy's picture

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.

dashish's picture

@luckysunda @shraddhagami @shiveshroy

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

More Comments
luckysunda's picture

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

shraddhagami's picture

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

sumitverma's picture

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.

rtiwari95's picture

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

wr=receiver window size 

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

dashish's picture

@pritam @sumitverma

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

More Comments
dashish's picture

@vinayrachapalli  The TT u might have seen is the transmission time of ACK from the receiver.

Go through the RTT definition then u will understand.

Just type "RTT definition" in google and u will get that.

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

chetnawadhwa's picture

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

dashish's picture

@chetnawadhwa

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

vivek14's picture

RTT is always 2*PT.

\(ɑ = { 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

anuraglahona's picture

wins the race means ,A takes less time?

shraddhagami's picture

Yeah if it takes less time then it's waiting time is less than B,therefore A wins.

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

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

jagmt's picture

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}

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 ?

shraddhagami's picture

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

anuraglahona's picture

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

sahastranshu's picture

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

More Comments
anuraglahona's picture

can anyone explain it?

pritam's picture

Here is a video illustration on this question: http://www.techtud.com/video-illustration/if-every-6th-packet-being-tran...

umangchaturv's picture

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

 

sudsho's picture

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

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

amit0368's picture

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

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

please subscribe to our youtube channel.

 

Responses

where is the quiz sir?

sumitverma's picture

Quiz is live now.

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

sumitverma's picture

Now you can see.

sumitverma's picture

Now you can attempt the quiz.

prajwalbhat's picture

I can't see Quiz icon,why?

sumitverma's picture

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.

 

dashish's picture

@amit0368 @pritam

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

amit0368's picture

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

dashish's picture

@amit0368

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

Enter your search keyword:

Search form

Wait!

Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.