The Message Is the Medium - Embedded.com

The Message Is the Medium

One way to describe a real-time system is to enumerate its interactions with its environment. Message sequence charts are a simple, rigorous, graphical, and intuitive notation specifically tailored to capture such interactions. MSCs are popular in telecom and, owing to similarities to UML, are used increasingly in many other domains.

Diagramming interactions with the environment is a common way to describe and understand an embedded system. Such a diagram is useful not only during system design but also for diagnosis if problems later arise. But how does one go about creating an effective diagram? Engineers need a simple, expressive, intuitive, graphical, and standardized notation system to specify interaction scenarios for embedded real-time systems. In this article, you'll learn the basics of one such notation system called the message sequence chart (MSC) and why you might want to try it.

MSC is a mathematically rigorous, yet simple diagramming technique. Popular in the telecom domain, MSC is increasingly used in real-time safety- and mission-critical systems. The sequence diagram and use-case scenario in UML are visually and semantically similar to the MSC notation.

Interactions and scenarios

When diagramming a description of an embedded or real-time system, we list the interactions between the system's environment and external systems, enumerating the interactions scenario-by-scenario. Two terms are important here: interaction and interaction scenario.

An interaction refers to a specific sequence of events that happens among participating entities. For example, one interaction might be a temperature gauge (an external system) sending a message to a system controller. The message would be one interaction. At more detailed levels, interactions involving internal components (subsystems) of the system are also included in the system description. For complex systems, these interactions can happen in a variety of ways.

An interaction scenario, on the other hand, details a specific group of interactions that form an episode and often stands for the possible event sequences in that episode. For example, an interaction scenario would be all the interactions between a pressure gauge, controller, and a valve that make the valve open when the pressure is too high.

Each interaction scenario is often classified as either desirable (“sunny day”) or undesirable (“rainy day”). Ideally, the implemented system should meet all the sunny day interaction scenarios and none of the rainy day ones.

Entities and events

In an MSC, entities are processes or subsystems, and events typically represent the sending and receiving of messages by entities. (Other kinds of events, such as timer-related events, also exist.) In an interaction scenario, you can think of an entity as an actor: it is a sender or receiver of events. An event, on the other hand, is the communication between the actors in the form of messages sent.

The meanings of process (or an instance, as it is sometimes called) and message depend on the system. A process does not necessarily stand for a computer program; it refers to any active agent. A message does not necessarily represent an actual data message; it may refer to another form of information exchange between entities. In the simplest case, a message has a name and no further structure or details.

An MSC is not concerned with the actual mechanism or channels of the message transmission, except to assume that the messages are always received in the order sent, without any loss or corruption. In MSC notation, the send (message) is nonblocking, which means the sender does not wait until the receiver receives the message.

An example

Figure 1 shows an MSC that depicts a simple interaction among three processes named valve, controller, and pressure_gauge. Each vertical line denotes the events that happen to the entity the line touches. The topmost event is the earliest event in time scenario, and the bottom event is the last. This temporal ordering of events for an entity is called its local order. The visual distance between the events within a local order is immaterial.


Figure 1: A simple message sequence chart

In Figure 1, the valve and pressure_gauge entities send their respective status to the controller using messages named status_close and status_high_pressure respectively. The controller then issues an open command to the valve using the message named cmd_open . This MSC depicts only one scenario; many others are possible-such as, for example, one where the valve is open, pressure is low, and the controller issues a command to close the valve.

What exactly is the scenario specified by this MSC? It may appear that the MSC represents only one scenario, only one sequence of message exchanges. The MSC, in fact, represents several message sequences, each of which captures the intended behavior. To understand this clearly, we define the notion of direct precedence among the events of the MSC.


Figure 2: (a) Events for MSC in Figure 1; (b) precedence graph for events

In Figure 1, there are three message send events and three message receive events; let us name these events as in Figure 2(a). We say that a send event directly precedes the corresponding receive event for a message. For example, e1 directly precedes e2. Also, for the events along the vertical line for the process valve, e1 directly precedes e6.

The precedence graph in Figure 2(b) captures these precedences among the events. The vertices of this precedence graph stand for events, and an edge (arrow) exists from event u to event v if u directly precedes v. An event v cannot occur until all preceding events have occurred. If the MSC is well-formed, the corresponding precedence graph is a directed acyclic graph (DAG); the precedence graph is also connected, which means there are no gaps, and has no self-loops or parallel edges. Given any two different vertices u and v, there is a path from u to v or from v to u. Since an event cannot precede itself, a self-loops, an edge from a vertex to itself, are forbidden.

Using the precedence graph, the events in an MSC can be classified into categories of minimal and maximal events. A minimal event has no preceding events, and a maximal event is not a precedent for any other event. For example, the events e1 and e3 are minimal events, and the event e6 is a maximal event. Two events are incomparable if there is no precedence relationship between them. For example, events e1 and e3 are incomparable, as are events e2 and e3.

Having defined the precedence graph associated with an MSC, we define a run R of an MSC M as a sequence of events in M such that each event in M appears exactly once in R, and, for any event in the sequence, all the preceding events adhere to the precedence graph for M. In general, there are several possible runs for an MSC. One formal meaning of an MSC is all its possible runs. For example, the MSC in Figure 1 has the following three possible runs:



Coregions

In Figure 1, the controller first receives the status_close message from valve and then receives the status_high_pressure message from pressure gauge. Sometimes, one may not wish any such ordering between these two events. The MSC notation allows one to avoid any particular ordering of a subset of events for a process by using a construct called a coregion.


Figure 3: An MSC with a coregion; associated precedence graph

A coregion is indicated by a dotted line segment within the vertical line for the process. Events within this dotted line are unordered. Figure 3 is a modification of Figure 1 using a coregion to make events e2 and e4 un-ordered; it also shows the associated precedence graph. Now, events e2 and e4 are incomparable and both directly precede e5.

Timers

Many scenarios relate message flows with timing constraints. You can easily specify such scenarios in the MSC notation using three special events: timer set, timer reset, and timeout. The timer set is denoted by an hourglass symbol connected to the timeline of a single entity. The timer reset is denoted by an X connected to the timeline. The timeout is denoted by connecting the hourglass symbol of the timer to the entity timeline by a bent line.


Figure 4: An MSC with a timer and coregion; associated precedence graph

Each timer has a unique name. For each timer, the timer-reset and timeout events must be preceded by the timer-set event. Also, timeout events have no other preceding events. In Figure 4, the controller starts a timer, t1, before waiting for messages from valve and pressure_gauge entities. The controller receives both messages and then resets the timer. Events e7 and e8 indicate the timer-set and timer-reset events. Figure 5 shows a simple MSC in which the controller sets timer t1 (event e7) and receives only the message status_close from valve before the timeout of timer t1 (event e9).


Figure 5: An MSC using a timeout; associated precedence graph

Conditions

A condition is an informal descriptive mechanism that displays a state or situation that must be reached by an entity or group of entities. A condition is written as a text label within a hexagonal box, which is placed either on a single entity or across a group of entities. If a condition C is placed on a single entity E, then E does not proceed to the next event until the condition is reached. That is, the condition C is a prerequisite for the next event in the entity. If the condition C is placed across a group of entities E1, …, Ek, then all the k entities must achieve local states in which C is satisfied. Only after that state is reached can any of the k entities proceed further in their respective local orders. In such a case, the condition C can be thought of as synchronization mechanism to ensure that the entities E1, …, Ek reach the same state before proceeding further.


Figure 6: (a) An MSC using conditions; (b) associated precedence graph

Figure 6 shows the MSC in Figure 1 (slightly rearranged), with the addition of some conditions. Entities valve and pressure_gauge share a condition called correct_status_available . Only when both these entities reach a state that satisfies this condition can they proceed further with their local orders. The entity controller must reach a state in which the condition ready_to_receive_status is satisfied before it can receive the status messages. The exact definition of these conditions is left out.

Inline operator expressions

Inline operator expressions are mechanisms that allow the end user to specify additional flow of control within the MSC and also to compose or combine multiple MSCs. Five types of operators can be used within inline expressions to specify flow of control:

  • alt (alternative composition)
  • par (parallel composition)
  • loop (iteration)
  • opt (optional region)
  • exc (exceptions)

Graphically, the inline operator expression is described within a rectangle that is horizontally divided using a dashed line; the operator keyword is written in the upper left corner.


Figure 7: An MSC having an inline expression with the alt operator

Figure 7 combines the MSCs in Figures 4 and 5 using the inline expression with the alt operator. The dashed line within the rectangle separates the two alternate paths; in a single execution, the MSC proceeds along only one of them.

Additional facilities

The MSC notation contains many more facilities than explained so far.

Messages can be sent to or received from the environment, rather than any specific entity. A message sent to the environment is depicted with its arrowhead ending up at the frame of the MSC. Similarly, the tail of a message received from the environment rests on the MSC frame.

The messages can include additional information. For example, the status_open and status_close messages sent by the valve process can be combined into a single message having the name status. The above two messages can then be represented as messages status(open) and status(closed) , where the argument contains the message value.

An MSC can include an action, which is a rectangle containing the textual description of some task to be performed. Like a condition, the action rectangle is placed on the vertical line of an entity. However, unlike a condition, an action is local; it can be attached only to a single entity and cannot span multiple entities. By treating actions as special kinds of events, one can include them in the precedence graph associated with the MSC. Like conditions, actions are often treated as informal descriptions.

Many other facilities exist in MSCs, such as gates for messages. Users can also describe an MSC in a standardized, event-oriented textual syntax, rather than the visual notation presented here.

High-level MSC

The basic MSC notation describes a small, specific elementary interaction. But what about complex systems? Well, just as a complex system is described as a hierarchical composition of subsystems, its interactions are described as hierarchical compositions of subinteractions.

High-level message sequence charts (HMSC) enhance the basic MSC notation in order to describe compositions of subinteractions. The HMSC notation also supports a top-down hierarchy in the sense that interactions can be specified at various levels of abstraction, starting at the highest and reaching down to the most elementary interactions described by basic MSCs.

An HMSC is a collection of nodes connected to each other through directed edges. Each node is either the start symbol -, the end symbol D, a rounded rectangle enclosing a reference to another lower-level MSC or HMSC, a hexagon enclosing a condition, a small empty circle denoting a connection point, or a parallel frame containing two or more HMSCs that act in parallel. To focus on the compositional aspect, entities are not shown in an HMSC. Connection points are mere conveniences to improve the layout. They have no semantics. Conditions in an HSMC are global in the sense that they apply to all the entities and indicate a global system state.


Figure 8: An HMSC example

Figure 8 shows an HMSC for the behavior of the controller in our example. The behavior is composed of several lower-level behaviors, which are specified by other HMSCs or MSCs. In this way, the HMSC notation allows top-down hierarchical decomposition of the behavior. The lower-level HMSC can contain further HMSCs or MSCs. Note that this HMSC does not contain an end symbol because the HMSC is cyclic. We have noted that the run of a basic MSC is always finite; this is not true for an HMSC, since an HMSC may contain cycles (indicating periodic or cyclic behavior).

Review and validation

Review and validation of the project requirements including those specified using MSCs, is a critical part of quality management. Here are two ways to review and validate the project requirements you've specified using an MSC:

  • Run a simulation, also called prototyping or animation, to test MSCs against specific scenarios
  • Ensure that MSCs satisfy specific system properties (laws)

In the latter, a tool can check the HMSC automatically. You can use notations related to temporal logic to state properties and use techniques such as model-checking and satisfiability to verify given properties. In addition, several special-purpose algorithms and tools can analyze the given HMSC to automatically detect a number of undesirable situations, such as deadlocks, race conditions, and nonlocal choice.

A shopper's guide

Message sequence charts provide a valuable service to engineers designing real-time safety- and mission-critical systems. Similar to sequence diagrams and use-case notation in UML, MSCs have several advantages over UML.

For instance, MSC simplifies the conceptualization of system requirements in the early design stages. MSC depicts the system as a single black box along with all other external entities with which the system interacts. The diagram contains only a brief, informal description of the system's interactions with its external environment. The black box and the external entities are treated as single entities in the MSCs, which means you do not need to know or specify anything about the internal structure or behavior of the system except whatever is known by its interactions. Such high-level black-box interaction-oriented system requirements are not well captured in UML.

MSCs also serve well as specifications of test scenarios (in integration testing, say). Since you can simulate, formally verify, or refine specifications using MSC, you can use MSCs widely within the life cycle of real-time embedded systems. Also, the MSC notation has been extended in several ways that may be useful for specific applications. For example, in timed MSCs, an upper and a lower time limit can be specified with each message, making it more suitable for protocols and real-time systems. Various documents can also be produced from a set of MSCs.

The MSC notation is popular in the telecom domain, but you can expect it to become more popular in the embedded sphere. esp

Girish Keshav Palshikar is a scientist at the Tata Research Development and Design Centre in Pune, India. He has an M.Sc. in physics from IIT Bombay and an MS in computer science and engineering from IIT Chennai. E-mail him at .

Resources

The ITU has released a standard for the MSC notation that includes formal mathematical semantics: ITU-T Recommendation Z.120: Message Sequence Chart (MSC), April 1996. Updated version at www.itu.int/itudoc/itu-t/rec/z/z120-es.html

Acknowledgements

I thank Prof. Mathai Joseph and Dr. Purandar Bhaduri for their guidance. The optimism of Dr. Manasee Palshikar has provided the impetus for this work.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.