discrete-event system formalism with concepts for states and events.
The paper is structured as follows: Section 8.2 motivates the framework by presenting a CPN model of a communication protocol. The model is used to illustrate some of the monitors which can be used, e.g. to gain knowledge about the behaviour of the model. Section 8.3presents the general monitoring frame-work for simulation models of discrete-event systems. Section 8.4 describes how the monitors presented in Sect. 8.2 can be realised using the general framework presented in Sect. 8.3. Finally, Sect. 8.5 concludes and gives directions for future work.
8.2 Example: Monitoring a Communication Proto-col
In this section, we will present an example model and then use it to illustrate how different monitoring tools can be used. Even though the model itself is fairly simple, many realistic and practical monitors can be used to inspect and modify the state of the model during simulations. The model is taken from [71]
which contains a detailed description of both the model and timed coloured Petri nets.
8.2.1 The Communication Protocol
The example that we will consider is a model of a simple communication pro-tocol. This protocol is used to ensure reliable transmission of packets across an unreliable network, i.e. a network in which overtaking and packet loss can occur. Each packet includes a sequence number which is used to ensure that packets are received once and only once, and in the proper order. After a packet has been received, an acknowledgement is returned to the sender. This acknowledgement contains the sequence number of the packet that the receiver expects to receive next. Since both packets and acknowledgements can be lost, the sender uses a timeout mechanism to trigger periodic retransmission of a packet which has not yet been acknowledged.
Figure 8.1 shows a timed CPN model of this communication protocol. The model was created in Design/CPN, in which prototype monitoring facilities have been developed. The model consists of aSenderpart (left-hand side), the Networkpart (middle), and a Receiverpart (right-hand side).
The sender sends packets (Send Packet), where a packet consists of a sequence number and the data to be sent. Moreover, the sender has a counter (NextSend) which indicates the number of the next packet to be sent. This counter is updated whenever an acknowledgement is received (Receive Ack). A constant timeout period of waitunits of time is defined, and a packet is retransmitted if an acknowledgement is not received within this period of time.
The network transmits packets (Transmit Packet) from the sender/network interface (A) to the network/receiver interface (B). Similarly, acknowledgements are transmitted (Transmit Ack) from the receiver to the sender. Packet loss is
Send
modelled by theOKfunction which is non-deterministic. The time that it takes to transmit packets and acknowledgements is determined by theDelayfunction.
Each time the receiver receives a packet (Receive Packet), it must decide whether to accept or reject the packet. For this purpose the receiver maintains a counter (NextRec) indicating which packet should be accepted next. If the expected packet arrives, then the packet is saved (Received), the counter is in-cremented, and an acknowledgement with the next expected sequence number is sent back to the sender. When an unexpected packet arrives, the packet is discarded, the counter remains unchanged, and an acknowledgement is sent back to the sender.
8.2.2 The Monitors
Several different types of monitors can be used both to control and modify a simulation of this model and to examine the behaviour of the model. All of the described monitoring activities could be incorporated directly into the model at the cost of modifying the model to contain states or events that are not found in the communication protocol.
In our work, we have observed a number of monitoring activities that can be described by the following categories, and specific examples of each category will be described in detail below. File access monitorsare used to read and write information in files. Simulation control monitorsare used e.g., to start and stop simulations, to determine the length of sub-simulations, or to select the order in which certain events occur. Visualisation monitorscan be used to visualise the
8.2. Example: Monitoring a Communication Protocol 85 Packet 1 received at time 190, EXPECTED
Packet 1 received at time 255, DISCARD - expecting 2 Packet 2 received at time 337, EXPECTED
Figure 8.2: Excerpt from the log file for the receiver.
behaviour of the system during a simulation, e.g. by updating message sequence charts or domain-specific graphics. Performance monitors measure and report on the performance of the system. Communication between a simulator and an external process can be controlled via communication monitors. Finally, property monitorscan be used to do functional analysis of a model. Functional analysis is concerned with proving that the system behaves as expected or that certain state and/or event properties hold for the system. Let us now consider specific examples from these categories of monitors.
Simulation Stop Monitor Suppose the simulation of the communication model should be stopped after a given number of packets have been received in the correct order. This type of stop criteria is completely dependent on the model and the system, in contrast to more general and model-independent types of stop criteria such as stopping after a given number of events have taken place or after a certain amount of model time has passed. Stopping a simulation after a certain number of packets have arrived using only general stop criteria would generally require modifying the model, e.g. by adding an event that could occur only after the required packets have arrived. In contrast, a simulation control monitor could be used to inspect either the states or the events of the system and then stop the simulation when the required packets had arrived without having to modify the model.
Log-File Monitor It may be useful to maintain a receiver log file containing information about the packets that were received. For example, the log file could contain the sequence numbers of the packets that were received, the time at which they were received, as well as noting which packets were received in the correct order. Figure 8.2 shows an excerpt from a file that was generated by a log-file monitor when simulating the protocol model. Such a log file could be used for debugging purposes or for analysing the system, e.g. for analysing arrival rates. A log-file monitor is a file access monitor which can only write strings in a file.
Message Sequence Chart Monitor MSCs have proven to be useful for visualising the behaviour of communicating processes. In the context of UML, MSCs are used for specifying communication patterns, while they are often used for analysing communication patterns within the context of CP-nets. MSCs provide a high-level view of communication patterns that may not be obvi-ous if one were restricted to inspecting every simulation event involving the communicating processes.
Communication Protocol (1)
Sender Network
Packet 1 lost
Receiver Send Packet 1
Send Packet 1
Transmit Packet 1
Receive Packet 1 Send Ack 2 Transmit Ack 2
Send Packet 1
Transmit Packet 1 Receive Ack 2
Receive Packet 1 Send Ack 2
Figure 8.3: MSC for communication protocol.
Figure 8.3is a MSC that was generated by a visualisation monitor. The MSC shows that the packet with sequence number 1 (Packet 1) was sent to the network by the sender three times. The first timePacket 1 was sent, it was lost on the network. Then Packet 1 was sent, transmitted across the network, and received by the receiver. The receiver responded by sending an acknowledge-ment with the sequence number for the next expected packet (Ack 2) back to the sender across the network. Finally, a timeout occurred, and Packet 1 was sent one last time before the acknowledgement from the receiver was received by the sender.
Data Collection Monitor Monitors can also be used to measure the perfor-mance of a system by collecting numerical data during a simulation. The data that is collected can be used to calculate statistics or saved in files which can be post-processed after a simulation finishes. For example, the protocol model could be used to measure the proportion of received packets that are discarded.
This performance measure could be of particular interest when using simula-tion to find a reasonable value for the timeout period when the approximate network delay and rate of packet loss are known. A data collection monitor, which is one type of performance monitor, measuring the ratio of discarded packets among all received packets would simply have to observe the events corresponding to the reception of packets (Receive Packet), and calculate the proportion of discarded packets in an appropriate manner.
Communication Monitors Communication with external processes can be very useful when simulating models of discrete-event systems, as the external processes can augment the functionality of the simulation tool in a variety of ways. For example, an external process could provide input or workload for the model, or the external process could also be used to process data that has been extracted from the model during simulation.
Communication channels can also be used for two-way communication be-tween a simulator and an external process. The external process could be, for
8.3. Monitoring Framework 87