Sliding Window Protocols? – Part 1

- There are many types of data transmission protocols of which one type is the packet based data transmission protocols. 

- These protocols have a feature called the sliding window protocol.

- The sliding window protocols are a great help wherever the in-order delivery of the data packets demand reliability. 

- For example, the Data link layer of the TCP (transmission control protocol) model and OSI model demand such reliability and thus use window sliding protocol. 

- According to the concept of the sliding window protocols, a consecutive number which is unique is assigned to each and every portion of the transmission i.e., the packets.

- These numbers are used by the receiver for placing the packets it will receive in their correct order. 

- Also, with the help of these numbers, the missing packets can be identified and the duplicate packets can be removed. 

- One problem regarding the sliding window protocols is that it has kept no limits for the size of these numbers that are required. 

- An unlimited number of data packets can be allowed to be communicated at any instant of time if limits are placed on the number of packets involved in transmission or reception. 

- By this, we mean using the sequence numbers of fixed size. 

- By term window we refer to the transmission side. 

- It actually represents the logical boundary or limit of the number of packets that the receiver has to acknowledge. 

- The transmitter has to be informed by the receiver for each ACK (acknowledgement) packet regarding the maximum size or the window boundary of the current receiver buffer. 

- For reporting the window size of the received buffer, a 16 bit field is used in the TCP header. 

- The maximum limit or boundary of the window that we can have is 2¹⁶ i.e., 64 KB. 

- When operating in the slow start mode, the counting of the transmitter begins with a low packet count.

- Gradually, the number of packets involved increases in every transmission after the ACK packet has been received. 

- Whenever it receives an ACK packet, the window slides logically by one packet for the transmission of a new packet. 

- On reaching the window threshold, one packet is sent by the transmitter for every one packet of ACK received. 

- Suppose the limit of the window is 10 packets and the transmitter is in slow start mode. 

- Then, first one packet will be transmitted followed by another two. 

- Between these two transmissions, it will send an ACK packet also. 

- This process will continue until the limit of 10 has reached. 

- After crossing the limit, the transmission is restricted to one i.e., for every ACK packet received only one data packet is transmitted. 

- When viewed during simulation, it seems as if the window is shifting by distance of one packet whenever an ACK packet is received. 

- For avoiding the traffic congestion, the sliding window protocol works up a great deal.

- In this way the application layer would not have to worry about transmission the next set of data packets. 

- It can continue to do so since the sliding windows of the packet buffer will be implemented on both the sides i.e., the receiver’s and the sender’s side by the TCP. 

-However, the network traffic influences the window size dynamically to a great extent. 

- In order to achieve the highest possible throughput, care should be taken for not forcing the transmitter to stop the transmission before one RTT or round trip delay time by the sliding window protocol. 

- The bandwidth delay product of the links in the communication should be less than the limit of the data amount that can be sent before sending ACK packet. - If this condition is not met, the links’ effective bandwidth will be limited by the protocol. 

Explain the methods for free space management? – Part 2

- Managing the free space is easy only when the space that has to be managed is divided in to units of fixed size. 

- If this is the case, the list of these fixed size units can be kept. 

- The first entry can be returned if it is requested by the client. 

- Managing free space gets difficult when the space to be managed consists of units of variable sizes. 

- This is the case with the memory allocation library at the user level. 

- This is also the case in the physical memory where the segmentation is used for the implementation of the virtual memory. 

- In such cases, external fragmentation is the main problem. 

- This leads to the splitting up of the disk space in to pieces of variable size. 

- The next coming requests might fail because of unavailability of contiguous free space. 

- For example, the request might fail even if 20 bytes are available and the request requires only 15 bytes because this 20 bytes space is non-contiguous. 

- Thus, the main problem is how the free space should be managed while satisfying the variable sized variables. 

How these strategies can manage free space while at the same time keeping the fragmentation in control.

Low level Mechanisms: 

- Most of the allocator use some common mechanisms as these: coalescing and splitting.

- Here, the free list consists of a set of elements describing about all the free spaces available in the heap. 

- Once a pointer to a space is handed over to the program, the determination of the pointers to this space becomes somewhat difficult. 

- These pointers are stored either in the registers or in the variables at some point of execution. 

- However, this is not the case of garbage collected and strongly typed languages as a measure for enabling compaction for combating fragmentation. - Suppose the program makes a request for a single byte of memory.

- In such a case the action performed by the allocator is called splitting. 

- Here a free memory chunk is searched for and split in to two. 

- The first one is returned to the calling request and the second one stays in the list itself. 

- This approach is used in the allocators where small requests are made requesting space that is of size smaller than the chunk. 

- Most of the allocators use a corollary mechanism called the coalescing of the free space. 

- Suppose a small heap is given and an application calls a function to obtain some memory. 

- This function returns the space available in the middle of the heap. 

- All these strategies are based up on simple policies. 

- An ideal allocator is the one that both minimizes fragmentation and is fast. 

- But since it is possible for the stream of free requests and allocation to be arbitrary, any strategy would go wrong if wrong inputs are given. 

- Thus, the best approach cannot be described. 

There are 4 major approaches in this regard:

1. Best fit: 

- Simplest and first searches the list for free chunks of memory that might be bigger than the size requested. 

- The smallest one in the searched ones is returned and this is known as the best fitting chunk or smallest fitting too. 

- One pass is enough for finding the appropriate block to be returned.

2. Worst fit: 

- This one is just the opposite of the best fit. 

- It looks for the largest chunk and returns the amount requested while keeping the remaining memory space.

3. First fit: 

- This one also looks for the first bigger block and out of it allocates the amount requested by the thread.

4. Next fit: 

- Here, one extra pointer is kept at the location where the last search was done. 

Explain the methods for free space management? – Part 1

- For efficient working of the programs and the entire operating system, it is important that the memory of the system should be managed. 

- When the files and programs are allocated memory space, some free space is left in the storage area. 

- It is required that these free spaces must be managed properly. 

- Since there is a limitation to the disk space, this same space has to be used again and again after deleting and creating new files. 

- A free space list is maintained by the operating system for keeping the track of the available free space. 

- All the free disk spaces are listed in free space list. 

- For the creation of a new file this free space list is searched in order to get the amount of space needed and then if the space is available, it is allocated to the file to be created. 

- In the case of deletion, after deleting the file, its space is added to the list of free spaces.

Methods for Free Space Management

There are 4 methods for the management of free space namely:

- Bit vector

- Linked list

- Grouping

- Counting

What is Bit Vector?

- Quite a many times, the free space list about which we mentioned above, is implemented as the bit vector (also known as the bitmap). 

- Here, 1 bit is used for representing each block. 

- If a particular block has been allocated to some file or program, its representative bit is set to 0 and when the block is available, the bit is set to one.

- Consider an example, suppose the following disk blocks are free and rest are allocated: 1, 2, 4, 5, 6, 7, 9, 10, 12, 13, 14, 18, 19, 21, 26, 27, 28. 

- Then for this allocation we have the following free – space bit map:

01101111011011100011010000111…

- This method of free space management is relatively simple and has good efficiency. 

- This method is known for its efficiency to locate the n consecutive free blocks or the first free block available in the storage area. 

- But this method can be inefficient if it is not kept in the main memory of the system. 

- Also, when required occasionally for the recovery needs, this map can also be written to the disk. 

- Keeping such maps in the physical memory is an easy thing if the system has a small memory but this is not always possible in the case of the systems with larger memories.

What is a Linked list?

- In this method, all the free spaces are linked together and the first block in this linked list is assigned a pointer which is stored in the cache memory. 

- Similarly, the pointer to the second block is stored in the first block.

What is Grouping?

- This method is a modified version of the free list approach and it stores the addresses of the all the free blocks in the first block that is free. 

- Here, actually the first n- 1 blocks only are free and the address of another n free blocks is stored in the last block. 

- This lets the system to find the addresses of a number of free blocks which is not possible in the case where the approach being used is the linked list approach.

What is Counting?

- This approach takes advantage of the simultaneous allocation or freeing of the contiguous blocks through clustering or by using contiguous allocation algorithm. 

- Thus, it requires only to keep the address of the first free block and the rest of the blocks follow it.