Sliding Window Protocols? - Part 3

In the third part of this article we shall discuss about the types of sliding window protocols and how these protocols can be extended?

1. Stop and Wait: 

- This one is the simplest type among all the sliding window protocols. 

- Under this type, we have the stop–and–wait ARQ protocol as the simplest implementation.

- Both the transmit window and the receive window is 1 packet and the number of possible sequence numbers required is 2 i.e., 1+1 = 2. 

- The packets sent by the transmitter are marked alternatively as odd and even. 

- Therefore, the ACK packets are in the series of odd, even, odd, even and so on. 

- Now, suppose the transmitter sends an odd packet and immediately without waiting for an odd ACK sends the next even packet. 

- In such a case, it would receive an ACK saying that an odd packet is expected. 

- This leaves the transmitter in a state of ambiguity i.e., whether the receiver got both the packets or none of them.

2. Go-Back-N ARQ: 

- This sliding window protocol has a fixed w_r  (fixed at 1) and w_r  which is always greater than one. 

- Here, the receiver will not accept any packet other than the expected one from the sequence. 

- If the packet gets damaged or lost during the transmission, then the packets following the lost ne will not be accepted by the receiver until and unless it receives the lost one after re-transmission. 

- This ensures minimum loss of 1 RTT (round trip time). 

- This is why it results in inefficiency in using this protocol on the links where the packet loss is quite frequent. 

- Suppose a 3 bit sequence number is being used as in typical HDLC. 

- This means number of sequence numbers is 8 starting from 0 to 7. 

- This also means we have 8 possibilities. 

- Enough ACK information is required by the transmitter for distinguishing between those packets. 

- If 8 packets are sent back to back by the transmitter without stopping for ACK, then it will find itself in the same doubt as in the stop-and-wait case.

3. Selective repeat ARQ: 

- This one is the most general case of the sliding window protocols. 

- It works with a receiver that is more capable of accepting packets having the sequence numbers greater than what the current n_r is and storing them till the gap is filled. 

- The advantage is that discarding data before re-transmission is not necessary.

Ways to extend these protocols

1. The above types of the sliding window protocols don’t talk about reordering the packets after receiving them all. This will ensure that they don’t appear in wrong order. If the long distance can be bounded, the protocols can be extended to support this feature. The maximum mis- ordering distance can be used to expand the sequence number modulus N.
2. Not acknowledging every packet is also possible after the sending an ACK up on not receiving packets. For example, every 2^nd packet is acknowledged in TCP.
3. Informing the transmitter immediately about the presence of gap in the packet sequence is quite common and so HDLC uses a packet called REJ packet for this purpose.
4. During the communication, the window sizes may change if their sum remains in the limit defined by N. usually the transmit window size is reduced for slowing down the transmission in order to keep with the speed of the links and preventing congestion or saturation. 

Sliding Window Protocols? - Part 2

As discussed in part 1 of this article, the sliding window protocol is a type of the packet based data transmission protocol. The sliding window protocols are used in regulating the reliability factor of the data transmission. 

In this second part we discuss about the motivation behind this protocol and how it actually operates. 

- There are a number of communication protocols based up on the automatic repeat request for regulating the error control. 

- In such protocols, it becomes necessary for the receiver for acknowledging about the packets it received. 

- If the receiver does not send an ACK to the transmitter within a specified time period, then the transmitter assumes that the packet might have got lost, re-transmits it. 

- It is obvious that if a transmitter does not receives an ACK for the packet it had sent cannot actually know if the packet got delivered correctly. 

- If, suppose corruption is detected during error detection process on the receiver’s side; the receiver will simply ignore this packet and hence, will not send any ACK to the transmitter. 

- Now in the same way, the receiver also does not know whether the ACK it sent was received by the transmitter or it got lost or damaged during the transmission.

-  In such a case, the re-transmission must be acknowledged by the receiver in order to prevent the continuous re-sending of the data by the transmission. 

- In other cases it is simply ignored.

How the protocol operates?

- The current sequence numbers say n_t and n_r is assigned to transmitter and receiver respectively. 

- Both of them have their window sizes say w_t and w_r respectively.

- In simple implementations of the protocols these sizes are fixed however, they may vary when it comes to the larger and complex implementations. 

- For making any progress, it is necessary that the size of the window must be more than zero. 

- In a typical implementation, n_t denotes the packet to be transmitted. 

- Similarly n_r denotes the packet not received. 

- Both of these numbers increase with the time monotonically. 

- The receiver also has to keep an eye on the highest sequence number that has not been received yet. 

- We have another variable called n_s which is one number greater than the highest sequence number that has been received. 

- There are simple receivers which accept the packets only in the order of w_r = 1 which is nothing but same as the n_r. 

- But in some cases it can exceed 1. 

Now we can say that:

1.     Below n_r no packets have been received.

2.     Above n_s no packets have been received.

3.     It is only between n_r and n_s that some packets have been received.

- Whenever a packet is received, its variables are updated appropriately by the receiver and at the same time an ACK is transmitted with the updated value of n_r. 

- Similarly we have variable n_a used by the transmitter for tracking the highest ACK it has received. 

- Below n_a all the packets have been received but there is uncertainty about the packets between n_s and n_a i.e, the n_r. 

- There are certain rules that are always obeyed by the sequence numbers:

Ø  N_a ≤ n_r: The highest ACK the transmitter has received cannot exceed the highest n_r recorded by the receiver.

Ø  N_r ≤ n_s: The partially received packets’ end cannot be greater than the span of those fully received.

Ø  N_s ≤ n_t: The highest packet sent is always greater than the highest packet received.

Ø  N_t ≤ n_a + w_t: The highest ACK received and the window size set the limits for the highest packet sent.

How do you invoke an application using TSL?

Test scripts of all the tests that are created via the winrunner are composed in a special programming language developed by the mercury interactive called the test script language or TSL. 

The generation of the test scripts in test script language (TSL) takes place while the recording of the test is in progress. Each line of the winnrunner test script that is written in TSL language is called a TSL statement and like in other languages each statement ends in semi colon. 

Most of the features of the TSL make it much like the C language but overall if we see, creating tests in TSL is quite easy as compared to writing tests in C. 

In this article we are going to discuss about how an application can be invoked using the TSL scripts.

- The TSL allows you to define a message in the test script of the test and have it delivered to the test results window through the winrunner. 

- For sending a message to the test results window, the below mentioned statement can be added in the test script:

Report_msg( message );

- The message may contain a variable, a string or a combination of both of them depending up on the desire of the user. 

- Applications can be started or invoked from a test script very easily. 

- The winrunner provides you a function for starting or invoking an application. - This function has been named as the “invoke_application” function. 

- The very presence of this function makes it quite easy for the testers to invoke the same or the other application that is being tested. 

- Mostly, it happens that you require to invoke the software application that is being test during the start up of the winrunner. 

- The application software that is being tested can be invoked very easily every time you start the winrunner software by just making an simple addition to the start up test that you are having at hand. 

- This addition is of the function that we discussed above i.e., the invoke_application. 

- The invoke_application can be added to the start up test and the application will be started by the winrunner.

(Startup tests or functions are those tests and functions which are run and executed by the winrunner before it starts running other main tests or functions. They mark the beginning of the winrunner testing.)

- If you are unable to add this statement to the test script of the start up test there is no need to worry as there is one more way for invoking the application being tested in winrunner.

-There is a “run” tab available in the test properties dialog box of the winrunner. 

- This run tab can also be used for invoking an application. 

- Clicking on this you can invoke the application at the beginning of some test run.

- If the run tab also fails then you have one more way of invoking the application being tested which involves the use of the system statement to start an application.

Now let us see what the syntax for the invoke_application function is, it has been stated below:

Invoke_application ( file, command_option, working_dir, show );

The explanation for the above function syntax can be given as following:

- The full path of the application software to be invoked is designated by the file.

- The command line options that are to be applied are designated by the command_option parameter.

- The working directory of the supplication software is designated by the work_dir.

- Lastly, what shall be the appearance of the main window of the application when it is open is designated by the show.

What is Earned Value Analysis (EVA) in Project Scheduling?

Earned Value Analysis(EVA) provides a quantitative indication of progress. The project manager uses this method to track the project. Proponents of the earned value system claim that it works for every software project irrespective of the kind of work. As a part of this, there is an initial estimation of the total number of hours of doing this project, with every task being given an earned value which is based on its estimated percentage of the total effort. In simpler terms, a project manager will be able to determine, through a quantitative analysis, how much of the project is actually complete.

As a part of this process, the following steps are needed to be done:
- The BCWS (Budgeted Cost of Work Schedule) is evaluated for each task that is included in the project. This estimation is done in terms of person-hours or person-days(if the effort is much more than a few hours). So, for a given work task its BCWS is the effort.
- All the BCWS that are calculated for all the tasks are summed up to get a value called BAC(Budgeted Completion).
- The next variable BCWP(Budgeted Cost of Work Performed) is calculated. The method to calculate BCWP is by taking BCWS value for all the tasks that have been completed(at any point in the schedule).

In simple terms, the difference between BCWS and the BCWP is that BCWS is the estimate for all task that was supposed to be done, while BCWP is the summary of all the activities that were completed.

EVA compares the planned amount of work with what has actually been completed, to determine if cost, schedule, and work accomplished are progressing as planned. Work is earned or credited as it is completed.

Earned Value Analysis
- compares like terms and is quick to apply in practice.
- requires the ongoing measurement of the actual work done.
- tasks that have not been started or that have been completed are relatively easy to quantify in terms of earned value.

Semaphores

Semaphores can best be described as counters used to control access to shared resources by multiple processes. They are most often used as a locking mechanism to prevent processes from accessing a particular resource while another process is performing operations on it.
A semaphore is a protected variable or abstract data type which constitutes the classic method for restricting access to shared resources such as shared memory in a parallel programming environment. A counting semaphore is a counter for a set of available resources, rather than a locked/unlocked flag of a single resource.
A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations : wait and signal. These operations were originally termed P(for wait) and V(for signal). The classical definitions of wait and signal are :
wait(S) : while S<=0 do no-op;
S=S-1;

signal(S) : S:= S+1;

Modifications to the integer value of the semaphore in the wait and signal operations must be executed indivisibly.
- Semaphores can be used to deal with the n-process critical- section problem.
- Semaphores can be used to solve various synchronization problems.

A mutex is a binary semaphore (a semaphore with capacity of 1), usually including extra features like ownership, priority inversion protection or recursivity. The differences between mutexes and semaphores are operating system dependent, though mutexes are implemented by specialized and faster routines. Mutexes are meant to be used for mutual exclusion (post/release operation is restricted to thread which called pend/acquire) only and binary semaphores are meant to be used for event notification (post-ability from any thread) and mutual exclusion.