### Computer Network | Capacity of Channel and Pipelining

#### Capacity of Channel

Capacity can be measured by counting number of packets of data embedded in a snapshot of a channel while it is transferring maximum amount of data it can hold. Which means the holding capacity of channel during transmission.

If a half duplex channel can send $$n$$ bits per second(Band Width) the it has a propagation delay($$T_p$$) of $$p$$ seconds, channel will have a capacity $$n*p$$ bits.

$$Capacity\ of\ channel = Band\ Width( BW ) * Transmission\ dealy( T_p )$$

Channels with high capacity is called thick channels/thick pipes and those with lower capacity is called thin pipes. Since the sender has to wait until receive acknowledgement from the receiver, in efficient usage of available space on thick pipes makes it not suitable for stop and wait protocol. We have efficiency( $$\eta$$ ) of stop and wait protocol, which can be rewrite as,

$$\eta =\frac{1}{1 +2\ a} =\frac{1}{1 +\frac{2\ T_p}{T_t}} \\ \\ \eta =\frac{1}{1 +\frac{2\ T_p\ BW}{L}} \\ \\ \eta =\frac{1}{1 +\frac{2\ T_p\ BW}{L}}=\frac{1}{1 +\frac{ ChannelCapacity }{L}}$$

For a full duplex communication link, Channel Capacity will be twice that of half duplex $$[Channel\ Capacity= 2\ T_p\ BW]$$ , since it can communicate to and fro at same time with out collision.

$$\Rightarrow$$ Efficiency of stop and wait protocol is inversely proportional to channel capacity. So it will give poor performance on a channel with higher capacity, this can be improved by a method called pipelining.

#### Pipelining/ Sliding window protocol

Let $$T_t = 1 \mu s$$ and $$T_p = 1.5 \mu s$$

If I apply stop and wait protocol for data transmission, $$\ \ efficiency\ \ \eta = \frac{1}{1+2a}= \frac{1}{1+2* \frac{1.5}{1}} = \frac{1}{4}$$

The efficiency is very less. The sender has used only small portion of the total time, because it has to wait during the to and fro transmissions until the acknowledgment from the receiver reaches at sender.

In order to increase the efficiency of the transmission this waiting time should be used for the sending of more number of packets and each of the packets transmitted from the sender has to be copied to the window buffer at the sender to keep track of its success rate of transmission, until its acknowledgment messages reaches at sender.

Data which are already acknowledged are stored pops out from the window, and inside the window we keep only those which are already transmitted and did not acknowledged till that time. So the number of such data packets defines the size of the window and which is a function of propagation and transmission delays.

By observing the timing diagram it is found that sender window size $$W_s = 1+ 2a$$

In order to identify data packet stored in window each of them should have a sequence number, which can be in increasing order of of natural numbers. But as the number of data packets grew up, the space to store sequence number will also become high. So it is a more convenient to use sequence number as minimum as possible with lower size. To do that sequence number last packet whose acknowledgement had received can be used.

$$Window\ size\ W_s = min( 1 + 2a, 2^N) \\ \\ N-\ Number\ of\ bits\ available\ in\ sequence\ number\ field \\ \\ Minimum\ sequence\ number\ required\ = 1 + 2a \\ \\ Bits\ used\ for\ number\ of\ sequence\ number\ = \left \lceil log_2(1+ 2a) \right \rceil$$

Q) Tt = 1 ms and Tp = 56.5 ms What should be sender window size to get maximum efficiency?

$$\\ a = \frac{T_p}{T_t} = \frac{56.5}{1}= 56.5 \\ \\ N = \left \lceil log(1+ 2a) \right \rceil = \left \lceil log_2(1+ 2*56.5) \right \rceil = \left \lceil log_2(114) \right \rceil = 7 \\ \\ Window\ size\ W_s = min( 1 + 2a, 2^N) = min( 114, 2^7) = min( 114, 128) = 114 \\$$

Notes:
Half Duplex
A half duplex communication medium is a channel which can be used either for sending data or receiving data at an instant, which means even though it provides bidirectional data path, the transmission time and receival time will be different.

Full Duplex
Full duplex channels are those transmission mediums where sending and receiving can be done simultaneously. Which means, the channel will have the capability to transport data from receiver to sender and from sender to receiver on same time.

### 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 …