Heuristic 1.1: Experimental Evaluation

Heuristic 1.1: The importance of protocol-state modelling raises with lower knowledge of the usage profile.

Summary of findings: Our experiments have shown that already a very little inaccuracy in the usage profile may lead to a very imprecise stateless (i.e. probabilistic-abstraction) model, since the inaccuracies can be easily magnified by system control flow. This is true for all the response-time metrics. There are two important arguments that justify the inclusion of the stateful information into the model in this case. First, significantly more effort is required in the stateless model to update its transition probabilities to a more accurate usage profile. Second, adaptation of the probabilities in the stateless model does not need to be sufficient to reflect the usage-profile change accurately. A structural change of the model may be needed.

Go back to the Stateful Software Performance Engineering website.

Example

Since this heuristic is generally valid for more state classes, we demonstrate its validity with the global state (the most general state class), which makes the models more compact and easier to understand. There are two statements underlying this heuristic. First, if the stateless model shall imitate the (realistic) stateful model accurately, the adaptation of model probabilities after a usage-profile update would not be sufficient, structural changes of the model are needed. At the same time such an adaptation is hardly feasible already in relatively small settings. Second, if the update shall only be reflected in the adaptation of model probabilities, the model can easily become very imprecise. This example validates the first statement, while the second statement is discussed below.

In particular, this example details a stateful model of a simple system and its stateless abstraction. The abstraction encodes the global states into a stateless model and is not loosing any information, but introduces significant structural changes to the model, which is demonstrated by this example (to justify the employment of a more simple information-loosing probabilistic abstraction in all the following heuristics). The encoding follows a standard encoding scheme, employed in process algebra to show that the expressive power of an algebra with and without value passing is identical [1].

Consider the model of a very simple library system in Figure 1 (with state-related actions marked blue). The model includes a simple usage scenario of a library visitor and two components with two services, findBook() and archiveSearch(). The usage scenario consists of three subsequent calls to the findBook() service. Before the three calls, the global state X is set to X=1 implying low complexity of the search in all the calls. FindBook() is modelled as a loop of two call actions to archiveSearch(), where the loop count is given by the global state X, whose value is in a changed way stored to the global state Y employed by the called archiveSearch() service. The internal behaviour of the archiveSearch() service is again modelled as a loop with a loop count given by the state value of Y.

Figure 1: Example of a Model with Global States X and Y

Encoding of the model in Figure 1 into a model without stateful parameters X and Y is depicted in Figure 2. Since findBook() only queries the value of X and archiveSearch() the value of Y, the actual values of the two global states in the moment of calling the services are encoded in the names that identify them. In particular, the model includes one instance of the findBook() service and two instances of the archiveSearch() service, each having the state value in its name, i.e. findBook1(), archiveSearch1() and archiveSearch2(). Notice that this encoding is only possible thanks to no concurrency in accessing X and Y.

Figure 2: Model from Figure 1 with Explicit Encoding of X and Y

Now consider a simple update of the visitor usage profile (depicted in Figure 3), changing the value of X before the second and third findBook() call to X=2 and X=3 (implying higher complexity of the search). The update of the model in Figure 2 to reflect this change is depicted in Figure 4. One can see that already in this very simple example, two simple changes in the usage model imply introduction of five more service models in Figure 4, with 23 new actions, comparing to the 5 actions of the original three services.

Figure 3: Model from Figure 1 after Update (Stateful)

Figure 4: Model from Figure 3 after Update (Stateless)

Discussion

One can easily see that already a minor change in the knowledge of the usage profile influences system behaviour significantly. This makes the precise encoding of a stateful information hardly feasible already in very simple systems. Moreover note that in the case of concurrent access to the global states X and Y in the example above, the employed encoding would not suffice to keep the model precise. Hence an information-loosing abstraction needs to be employed.

The most intuitive abstraction is the probabilistic abstraction in which no structural changes are needed - only the state-dependent conditions guarding the control-flow decisions (branches, loops) are replaced with probabilities. Such probabilistic abstractions of the models from Figure 1 and 3 are depicted in Figure 5 and 6.

Figure 5: Simple probabilistic Abstraction of the Model from Figure 1

Figure 6: Simple probabilistic Abstraction of the Model from Figure 2

However, even if the probabilities are estimated as precisely as possible, the models can become very imprecise, which is the second statement underlying this heuristic. This is mainly due to the lost information about the correlation of control-flow decisions guarded by the same state. Since this fact is illustrated by all the remaining heuristics, starting with Heuristic 2 for the protocol state specifically, we reference the experiments of this heuristic and do not discuss the details here.

References

[1] R. Milner, Communication and Concurrency. Prentice Hall, 1989, iSBN 0-13-115007-3.