Skip to main content

Computer Network | Flow control Methods: Stop and Wait

Some times sending data packets at higher rate to a less efficient receiver may cause for the discarding of data from the buffer and lead to data loss. Flow control methods are used to avoid this dilemma.

Stop and Wait

When the data packet from the sender reaches at the receiver it returns a success message and once the sender acknowledges the success return it will go for the the next one. This sequence of protocols are know as stop and wait method of flow control.

In theoretical questions Tq and Tprocess usually approximates as zero. Generally Transmission delay for the acknowledgement will be negligibly small (about 10-3 times) compared to transmission delay for the data,which may also can approximate to zero.

Piggybacking is a concept where data is send along with acknowledgment and other control information during bidirectional communication. So in Piggybacking acknowledgement time will become equal to that of propagation transmission time.

Cases where Tacknowledgement, Tq and Tprocess is approximated as zero, total time can be written as

Ttotal = Tt- data + 2 *Tpropagation

A better control method makes efficient communication. Here, as propagation delay become larger, the sender have to wait much longer to send next packet of data, which leads to a inefficient communication.

Efficiency η = useful time/ total cycle time

η = TtTtotal time = Tt (Tt+ 2 Tp) = 1(1+ 2 (TpTt))= 1(1+ 2a) [ a = TpTt ]

In networking throughput is the amount of bits a system is able to send in seconds.

Throughput = L(Ttotal) =(L/BW)*BW(Ttotal) = (Tt-data) * BW(Ttotal)=η* BW

Some times throughput is also called effective bandwidth or bandwidth utilization

  • The efficiency will decrease with increase in distance between sender and receiver, so stop and wait flow control method is better with LAN and less efficient for WAN.
  • As the size of data packet increases the efficiency of stop and wait flow control method becomes high, so its is better for larger packets of data.

Failures and solutions of stop and wait

The protocols of wait and stop flow control methods defined as, after sending a data packet to receiver, the sender has to wait until the acknowledgement is get back to the sender from the receiver as described above.

Case 1: Data missing

By any cause if the "data" get missed in between sender and receiver, the receiver will wait for the data and sender will wait for the acknowledgement and both of them will get into a deadlock.

To avoid the deadlock usually will go with a "time out timer", so that if the acknowledgement did not receive with in specified time out time the device will consider it as data loss and continue with next packet. This method with addition of timer is known as S&W with ARQ (stop and wait with automatic request).

Case 2: Duplicate packet problem

Suppose the data send by sender is received and receiver and it had replied with acknowledgement, but but what if during the propagation the acknowledgement it get lost?, sender will continue to send same data after specific duration declared on time out timer and it causes for the duplication of data multiple times at the receiver. This scenario is called "duplicated packet problem".

Addition of unique sequence number to the data packets, makes each packets distinguishable for receiver, hence the duplication can be eliminated.

Case 2: Delayed acknowledgement

Suppose sender had send a packet of data D1 and by some reason its acknowledgement A2 got delayed , by the way 'time out timer' triggered the resenting of same data packet (say D1') second time and you got its acknowledgement A2'. Acknowledging of A2' turned to sending of next packet of data D2 and before reaching its real acknowledgment A3 if delayed acknowledgment A2 reaches at the the sender it may misunderstand A2 as A3 and may go for sending of next packet.

In order to remove this issue, with each acknowledgment has to be named with sequential id numbers, so that it is differentiable to the sender.

So Along with Stop and wait algorithm if we use time out timer, sequential ID for data and acknowledgment all of communication problems can be resolved.

Comments

Popular posts from this blog

Operating Systems | Scheduling Algorithms : Round Robin

| FCFS | SJF | SRTS | Round Robin | LJF | Priority Scheduling | HRRN | Round RobinFeatures : Most popular algorithm of allPractically implementableImplementable with basic data structures like queueExtremely lesser starvationOptimum efficiency can be set by controlling time quantumThe round robin algorithm will continuously switch between processes if a process in CPU (under execution) exceeds a time limit set by OS called time quantum.Flow Chart :Scheduler allocated process to for execution.CPU starts monitoring the execution time right after from allocation.If the process completes its execution before exceeding time quantum, OS forwards the process to termination state.else, the processes gets preempted once the time quantum limit exceeded and if the process finished at this moment, OS moves the process to termination state, else it moves to ready queue and iterates over the whole process listed above.Example : Consider the following table of processes and calculate complet…

Operating Systems | Concept of Process

Hard disk drive of the system in called primary memory and secondary memory is Random Access Memory(RAM). Either a program written in High Level Language(HLL) or a executable code generated by the sequence of works done by pre-processor, compiler and assembler, resides in secondary memory of the system. To start an execution, operating system allocates some space in the main memory, for the program to be executed and loads the program in the secondary memory to the allocated space. The piece of work which is loaded by the operating system to the main memory in order to execute program is called processEvery program loaded by operating system will create a focus boundary(or process body), a partitioned memory area where all memory requirements for the execution of program is satisfied.Variable which will not change its value through out life time of process is called static variable and variables which are globally accessible in a process known as global variable.Heap area is reserved f…

Operating Systems | Scheduling Algorithms : SJF

| FCFS | SJF | SRTS | Round Robin | LJF | Priority Scheduling | HRRN | Shortest Job First(SJF)SJF algorithm schedules the shortest job(low burst time) available on main memory at the time of context switching in ready state . It can be either preemptive or non-preemptive depending on the nature of scheduler.Since the SJF select the job which is shorted among available jobs on main memory, Non-preemptive SJF algorithm will have larger waiting time if a job with longer burst time get scheduled first. In short SJF is also vulnerable to Convoy EffectTo find shortest process among min-heap would be the best data structure to be usedExample : Consider the following table of processes and calculate completion time, turn around time and waiting time using SJF algorithm with the following assumptions. No preemption.No I/O request will be there from any process.Arrival time is relative to CPU on time.Process NumberATBT103222324442View Answer

The execution of processes can be visualized …