OpenTTCN/Knowledge base/Interleave Tutorial

From OpenTTCN

OpenTTCN DocZone   Home | Developer's corner | Knowledge base | Working documents | Documentation | OpenTTCN IDE | Tutorials | Training | How do I | Frequently asked questions | Technical support

Interleave Tutorial

---

This article discusses the rationale behind the TTCN-3 interleave statement defined by ETSI ES 201 873-1 (Core Language) and ETSI ES 201 873-4 (Operational Semantics) standard suite. In this article we explain what interleave really means and how to use interleave. We accompany our explanation with examples of interleave.

Need for specifying interleaved behaviour

There are cases when the same communication channel can be used by several entities at the same time, e.g. for streaming several input streams. Usually such input data is multiplexed and sent over a shared channel as a sequence of interleaved segments. A substantial property of such multiplexed stream is that segments of one input stream may arrive at the receiving side in any relative order with regard to segments of another input stream, however relative ordering of segments from the same input stream is preserved both in multiplexed and demultiplexed streams. This is illustrated by explanation that follows.

Suppose we have two finite streams A and B consisting of 5 segments each, as illistrated by Tables 1 and 2.

Table 1: Segments of stream A

A1

A2

A3

A4

A5

Table 2: Segments of stream B

B1

B2

B3

B4

B5

Legitimate variants of a multiplexed sequence of both streams are presented in Table 3.

Table 3: Variants of multiplexing streams A and B into one stream

Variant 1 (1-1, stream A first)
A1	B1	A2	B2	A3	B3	A4	B4	A5	B5
Variant 2 (1-1, stream B first)
B1	A1	B2	A2	B3	A3	B4	A4	B5	A5
Variant 3 (2-2, stream A first)
A1	A2	B1	B2	A3	A4	B3	B4	A5	B5
Variant 4 (full stream A first, full stream B next)
A1	A2	A3	A4	A5	B1	B2	B3	B4	B5
Variant 5 (random interleaving)
A1	B1	B2	A2	A3	B3	A4	A5	B4	B5
Variant 6 (1-4-4-1)
B1	A1	A2	A3	A4	B2	B3	B4	B5	A5
Variant 7 (4-1-1-4)
A1	A2	A3	A4	B1	A5	B2	B3	B4	B5

The list of variants presented in Table 3 in not exhaustive.

Counting N, which is the number of all possible variants of a multiplexed stream presented in the example above, is a subject of domain in combinatorial mathematics dealing with partially ordered sets and constrained permutations of elements, or segments of streams in our case. This is discussed later in the "Combinatorial explosion" section in more detail.

The amount of possible ways to interleave or multiplex several streams into one, which can be large at times, poses a challenge to a behaviour specifier to describe such situation in a compact way. This is what interleave is primarily intended for.

Modelling receipt of interleaved sequence in TTCN-3

TTCN-3 has a built-in support for defining expected behaviour of an SUT that multiplexes several streams into one by offering the interleave construct.

TTCN-3 interleave is syntactically similar to alt. Semantic differences are bigger though. Receiving operations in all interleave branches must match before execution of interleave completes. Receiving operations in different branches of the same interleave construct may match in any relative order with regard to receiving operations in other branches. Receiving operations from the same branch must match in the same relative order as they are declared in the branch. Branching through if/elseif/else and alt inside interleave is allowed, requiring that only one such branch can be executed.

All these powerful features of interleave make it possible to use TTCN-3 interleave construct directly to specify the expected behaviour of a multiplexing sender (SUT) presented in the previous section. Here is how it can be done in TTCN-3:

interleave
{
    [] p.receive("A1")
    {
        p.receive("A2");
        p.receive("A3");
        p.receive("A4");
        p.receive("A5");
    }
    [] p.receive("B1")
    {
        p.receive("B2");
        p.receive("B3");
        p.receive("B4");
        p.receive("B5");
    }
}

The construct above covers all reception cases presented in Table 3 of the previous section.

Each interleave branch in the code excerpt above effectively describes one original stream in a multiplexed sequence (see Table 3) prior to its multiplexing.

Authors of the standard intentionally limited ability to use control flow transfer statements inside interleave. Nested interleave statements are allowed though.

TTCN-3 standard conceptually describes interleave through its compile-time expansion into an equivalent set of alt statements, although tools are free to implement interleave the way they see fit, which is, in fact, the case with OpenTTCN. Conceptual expansion means that default attachment through activated altsteps is allowed, like for any other regular alt. As of date of writing this article, there are two pending change requests at ETSI, CR5807 and CR5833, which make it clear that the repeat statement is allowed in activated defaults, a feature already supported by OpenTTCN.

Combinatorial explosion

If we approach the task of counting N, the number of all possible variants of a multiplexed stream presented in the example in the "Need for specifying interleaved behaviour" section, as a problem of counting all possible variants of inserting segments of stream B into original stream A consisting of n = 5 segments, and hence p = n + 1 = 6 insertion points, starting with single-segment stream B consisting of m = 1 segments, then for different variants of m, the seeked N, which is the number of ways to represent the desired multiplexed stream, would be:

For m = 1:

For m = 2:

For m = 3:

For m = 4:

For m = 5:

For arbitrary m:

This formula works for two interleaved streams with an arbitrary number of segments in each, m < p. For our concrete example:

i.e. approximately 65 ways of representing the interleaved sequence in question.

These numbers will clearly be bigger if more than two sequences are being interleaved. For example, number of ways to interleave t single-segment streams is equal to the number of permutations of a set with t elements, or t! (factorial of t). For 10 single-segment streams this yields 10! = 3 628 800 possibilities.

As sequences grow longer, number of ways to receive them also grows. Combined with growth in number of sequences subject to multiplexing into one stream simultaneously, this may lead to combinatorial explosion, what poses threats to brute-force implementations of interleave in TTCN-3 tools if expansion into a set of alt statements is performed literally at compile-time.

OpenTTCN uses dynamic approach to implementing interleave, handling it natively in the virtual machine rather than expanding it at compile-time, what makes the tool not subject to such combinatorial explosion even if long sequences of messages are involved, or if there are many sequences interleaved at once, or if there are both.

Debugging Interleave

It is easier to understand how interleave works in practice by specifying example interleave construct in your tryout test suite, sending it messages in a crafted sequence one by one from the peer PTC and seeing in OpenTTCN debugger how the state of evaluation of interleave changes depending on which messages are already received and processed.

OpenTTCN Tester IDE ships with the Demo3 example containing TC_interleave and TC_interleave_2 test cases demonstrating use of interleave.

Here is how TC_interleave_2 looks like:

function TC_interleave_2_PTC() runs on Comp_PTC
{
    port_B.send("MySig4");
    port_B.receive("MySig5");
    port_B.receive("MySig6");
    port_A.send("MySig1");
    port_A.receive("MySig2");
    port_B.send("MySig7");
    port_A.send("MySig3");
}

testcase TC_interleave_2() runs on Comp_A system TSI_A
{
    activate(AS_activate());
    T_NOAC.start(10.0);

    var Comp_PTC ptc := Comp_PTC.create alive;

    connect(mtc:port_A, ptc:port_A);
    connect(mtc:port_B, ptc:port_B);

    ptc.start(TC_interleave_2_PTC());

    interleave
    {
        [] port_A.receive("MySig1")
        {
            port_A.send("MySig2");
            port_A.receive("MySig3");
        }
        [] port_B.receive("MySig4")
        {
            port_B.send("MySig5");
            port_B.send("MySig6");
            port_B.receive("MySig7");
        }
    }
    
    setverdict(pass);
}

The interleave example presented above works as follows, as can be verified in OpenTTCN debugger:

• initially, either "MySig1" or "MySig4" is expected to arrive (waiting state S1);

• after "MySig4" is received, "MySig5" and "MySig6" are sent, and after this, either "MySig1" or "MySig7" is expected to arrive (waiting state S2);

• after "MySig1" is received, "MySig2" is sent, and after this, either "MySig3" or "MySig7" is expected to arrive (waiting state S3);

• after "MySig7" is received, "MySig3" is the last one expected to arrive (waiting state S4). Note though that at all times of evaluating interleave the AS_activate() altstep was activated as a default, so whenever interleave was entering a state when it was expecting an alternative from a list to arrive (states S1, S2, S3, S4), an unexpected input would trigger a branch in the default as it would do for a regular alt statement;

• after "MySig3" is received, interleave is done, so instruction pointer moves to the next statement beyond interleave (setverdict(pass) in our case) and proceeds with the execution.

Figure 1 illustrates debugging of interleave using OpenTTCN debugger. Interleave being debugged on Figure 1 is in waiting state S3 as described above.

Fig. 1. Debugging interleave. Interleave is in waiting state S3 (click to see larger image)

Interleave tips and tricks

• Avoid using interleave if behaviour can be more conveniently specified using plain set of alt constructs. Interleave is still rarely used in real-world test suites and it has a moderately steep learning curve, what may affect readability of the test suite and have maintenance impact.

• Do not hesitate to use interleave to specify complex multiplexed streams of input data - this what interleave is meant for.

• Use repeat in activated defaults to filter out ignored input.

• Add timeout events to activated defaults rather than to interleave branches themselves to help readability and simplify maintenance.