Pipeline Computing And Protocol

Pipeline Protocol

Today I will begin explaining Pipeline Computing And Protocol by a hypothetical scenario: Suppose an application wants to send a file of 8MB size, packet size equals to 10000bits, Round Trip Time (RTT) equals to 40msec and data rate / bandwidth equals to 1Gbps.

In the above scenario, next packet is sent by the sender after receiving the acknowledgement of the previous one.

Now let us calculate the efficiency of utilizing the bandwidth:

(Us) Utilization Sender =            L/R                   
                                                 RTT + L/R

Where, L= Length of Packet, R = Bandwidth / Data rate and RTT= Round trip time

Us =            10000/10^9                          = 0.000249938
(40 x 10^-3) + 10000/10^9

Bandwidth Utilization = 10^9 x 0.000249938 = 249937.5 bps = 249.9375 Kbps

The problem with above scenario (stop and wait protocol) is that the waiting time is very long, due to which, out of 1 Gbps the sender is only utilizing 249.9375 Kbps of the bandwidth and remaining is getting wasted.

We can optimize the above scenario by keep on sending the packets and not waiting for the acknowledgement. The sender buffer starts pushing multiple packets into a network and at the other hand the receiver buffers starts sending the acknowledgement packet as soon as it receives data packets from the sender. So in a way, we are utilizing RTT and instead of just sending one packet, we are sending burst of packets. This is known as pipeline protocol.

Suppose sender sends burst of packets through pipeline protocol, however, in the middle few packet in different orders gets lost. Then what?

Solution:

We can have two possible solutions to the above problem.

1. Send only those packets which are not received. Such kind of protocol is known as selective repeat protocol. The sender retransmits only those packets which were lost / whose acknowledgements were not received. This protocol will further be explained in the topic Selective Repeat protocol.
2. Resend all packets. This kind of protocol is known as Go Back N protocol. Suppose the sender wanted to transmit 10 packets to the receiver, 4 packets were transferred and acknowledged, however the 5^th acknowledgement was not received, the sender, after the expiry of timer, will resend all the packets from 5^th to 10^th and this will continue till all the packet acknowledgement is not received; so it’s like go back to the N^th packet and send the burst of packets from there.  This protocol will further be explained in the topic Go Back N protocol.

Application layer does not ensure reliable delivery, neither IP does, it is the transport layer that stores data and ensures the reliability of data transfer.

In the above fig, places of packet No. 1, 3 and 4 are empty so the transport layer now request application layer to send more chunks of data, as the packets here have already been acknowledged. But at places 2, 5 and 6 new data can’t come, because if time out occurs, the sender will need the same previous data for retransmitting.

For the receiver buffer, those packets which have been acknowledged, they will be delivered to the application and if the receiver gets duplicate packets, then one packet will be discarded.

Pipeline protocol has the following consequences:

Sequence Number:

The sequence number is required as the packets are sent in bulk and may not be in a sequence when traveling through pipeline and therefore to rearrange the packets in proper sequence.

Buffering:

The packets that are being transferred from the sender to the receiver needs to be buffered at both ends. At the sender end, buffer is required to store the data and wait till all packets acknowledgement has been received by the sender. On the other hand buffer is required to store the data till all of the packets are correctly received by the receiver and then the complete final data is provided to the application layer.

 Range of the sequence number and size of the buffer:

The sequence number is required to identify the packets received by the receiver and to sequence the data accordingly. But here a question arises that what should be the maximum number used for the sequence and what should be the size of the buffer holding such packets? In TCP protocol, sequence number is of 32 bits, therefore maximum number of packets at a time can be 2^32 = 4294967296 packets. Suppose, we have 8 bit sequence number, then this means we can have 2^8 packets.

For Further