Performability Analysis of An Event Demultiplexing Pattern

Swapna S. Gokhale^{∗}^{†}  Aniruddha Gokhale  Jeff Gray
Dept of CSE  Dept. of EECS  Dept. of CIS
Univ. of Connecticut  Vanderbilt Univ.  Univ. of Alabama
Storrs, CT 06269  Nashville, TN 37235  Birmingham, AL
ssg@engr.uconn.edu a.gokhale@vanderbilt.edu gray@cis.uab.edu

Abstract

The growing reliance on services provided by software applications places a high premium on the reliable and efficient operation of these applications. A number of these applications follow the eventdriven software architecture style since this style fosters evolvability by separating the event handling from event demultiplexing and dispatching functionality. The event demultiplexing capability, which appears repeatedly across a class of event-driven applications, can be codified into a reusable pattern, such as the Reactor pattern. In order to enable performability analysis of event-driven applications at design time, a model is needed that represents the event demultiplexing and handling functionality that lies at the heart of these applications. The model must also consider failures in order to provide realistic performance or performability estimates. In this paper, we present a performability model of the Reactor pattern based on the well-established Stochastic Reward Net (SRN) modeling paradigm. We illustrate the use of the model for the performability analysis of a virtual private network service based on the concept of a Virtual Router.

1 Introduction

Society is increasingly dependent on capabilities provided by distributed software applications that enable critical services (e.g., electric power grid, air traffic control, mobile communications). Due to the growing reliance of our daily activities on these services, efficient and reliable operation of the applications that provide these services is crucial. A number of these applications are event-driven software systems [9]. The event-driven style constitutes a provider/listener model [3], where the application listens for service requests or “events” and provides the necessary services in response to these requests or events. Event-driven systems provide many advantages, the most prominent advantage being evolvability, which is enabled by the separation of event demultiplexing and dispatching from event handling. Although the handling of events is specific to the services provided by the application, the event demultiplexing and dispatching functionality is more or less uniform across all the applications that follow the event-driven style, and can be codified into a reusable building block or a pattern [2]. The Reactor pattern [15] embodies the demultiplexing and dispatching capabilities that could be reused to facilitate the development of event-driven applications.

∗Contact Author †This research was supported in part by a grant from the National Science Foundation, NSF-CNS #0406376

It is a well-known fact that it is important to analyze the performance of an application starting from the early phases of the life cycle [18]. Moreover, pure performance analysis, which does not consider application failures leads to optimistic performance estimates. Thus, it is important to consider application failures during performance analysis in order to provide realistic “performability” estimates [16]. Design-time performance analysis is almost invariably based on a model that represents application behavior. As a result, in order to enable model-based performance analysis of event-driven applications, it is necessary to build a model of the underlying event demultiplexing framework that is ubiquitous in such applications.

In this paper we present a performability model of the reactor pattern, which provides the event demultiplexing and dispatching capabilities. The model is based on the Stochastic Reward Net (SRN) [13] modeling paradigm. In addition to the event demultiplexing capabilities, the model also considers application failures during event handling. The concept of a Virtual Router (VR) [8], as used in virtual private networks, is used as the guiding example of an event-driven system. The VR can leverage the reactor pattern for its design and implementation. We illustrate how the SRN model of the reactor pattern could be used for the performability analysis of the VPN service provided by the VR.

This paper is organized as follows: Section 2 describes a real-world distributed system that illustrates event-driven features; Section 3 describes related work and provides an overview of the Stochastic Reward Net (SRN) modeling paradigm used to build the performability model of the reactor pattern; Section 4 introduces the process to build a performability model of the reactor pattern; Section 5 illustrates how the SRN model could be used for the performability analysis of the VPN service provided by the virtual router system that uses the reactor pattern; and finally Section 6 provides concluding remarks outlining the lessons learned from this study, as well as directions for future research.

2 Overview of Event Demultiplexing Patterns

This section describes the event demultiplexing patterns found in real-world systems, such as a virtual private network service that uses the virtual router concept [8]. Section 2.1 provides an overview of the virtual router to illustrate the event-driven nature of the service. Section 2.2 then presents an outline of the reactor pattern [15] found in many large distributed systems like the virtual router-based VPN.

2.1 Description of the VPN Service

Figure 1 illustrates the architecture of a provider-provisioned virtual private network (PPVPN) [1] using a VR. A VR is a software/hardware component that is part of a physical router called the provider edge (PE) router. A VR contains the mechanisms to provide highly scalable, differentiated levels of services in VPN architectures. Multiple VRs can reside on a single PE device. VRs can be arranged in a hierarchical fashion within a single PE as shown in Figure 1. Moreover, an entity acting as a service provider for an end customer might itself be a customer of a larger service provider. VRs may also use different backbones to improve reliability or to provide differentiated levels of service to customers.

Figure 1: VPN Architecture using Virtual Routers

Customer edge (CE) devices (e.g., workstations or handhelds) wishing to join a VPN connect to a VR on the PE device. A VR can multiplex several distinct CEs belonging to the same VPN session. A VR may use tunneling mechanisms to use multiple routing protocols and link layer protocols (e.g., IPSec, GRE, and IP-in-IP) to connect with the CEs. A totally different set of protocols and tunneling mechanisms could be used for inter-VR or VR-backbone communication. These tunneling mechanisms can also be the basis for differentiated levels of service, as well as to provide improved reliability. A VR also comprises firewall capabilities.

The architecture of the VR is aptly suited for event-driven systems, which requires demultiplexing and dispatching events to the correct event handler in a VR. For example, requests to join a VPN are a type of an event that must be handled by the VR. Events indicating arrival of data are yet another type of event that must be handled by forwarding the data to the correct next hop in the VPN set up.

The VR-based VPN illustrates an event-driven system that must be reliable and that can be designed and implemented using reusable event demultiplexing and dispatching patterns, such as the reactor.

2.2 Description of the Reactor Pattern

Figure 2 depicts a typical event demultiplexing and dispatching mechanism documented in the reactor pattern [15]. The application registers an event handler with the event demultiplexer and delegates to it the responsibility of listening to incoming events. On the occurrence of an event, the demultiplexer dispatches the event by making a callback to the correct application-supplied event handler. This is the idea behind the reactor pattern, which provides synchronous event demultiplexing and dispatching capabilities.

Figure 2: Event Demultiplexing Pattern

Figure 3 illustrates the reactor pattern dynamics. We categorize these dynamics into two phases described below.

1. Registration phase: In this phase all the event handlers register with the reactor associating themselves with a particular event type they are interested in. Event types usually supported by a reactor are input, output, timeout and exceptions. The reactor will maintain a set of handles corresponding to each handler registered with it.

2. Snapshot phase: Once the event handlers have completed their registration, the main thread of control is passed to the reactor, which in turn listens for events to occur. A snapshot is then an instance in time wherein a reactor determines all the event handles that are enabled at that instant. For all the event handles that are enabled in a given snapshot, the reactor proceeds to service each event by invoking the associated event handler. There could be different strategies to handle these events. For example, a reactor could handle all the enabled events sequentially in a single thread or could hand it over to worker threads in a thread pool. After all the events are processed, the reactor proceeds to take the next snapshot of the system.

Figure 3: Reactor Pattern Dynamics

Many different variations of the reactor pattern are possible. These variations stem from the different event demultiplexing and event handling strategies used in a reactor. For example, in network-centric applications, networking events can be demultiplexed using operating system calls, such as select or poll. For graphical user interfaces (GUIs), these events could be due primarily to mouse clicks and can be handled by GUI frameworks like Qt or Tk. On the other hand, the event handling mechanisms could involve a single thread of control that demultiplexes and handles an event, or each event could be handled concurrently using worker threads in a thread pool or by thread on demand.

In this paper, we have developed a performability model of the reactor pattern, which uses the select system call for event demultiplexing and uses a single thread of control to demultiplex and handle events identified in a given snapshot. In the rest of the paper we describe this model and demonstrate the use of the model for performability analysis.

3 Background and Related Work

This section provides an overview of the Stochastic Reward Nets (SRN) [13] modeling paradigm used for the performability model of the reactor pattern. SRNs represent a powerful modeling technique that is concise in its specification and whose form is closer to a designer’s intuition about what a model should look like. Since a SRN specification is closer to a designer’s intuition of system behavior, it is also easier to transfer the results obtained from solving the models and interpret them in terms of the entities that exist in the system being modeled.

SRNs are an extension to Petri nets [12]. Petri nets were proposed to represent formally the flow of control in a system. A Petri net is a directed graph which comprises two types of elements, namely, places and transitions. A directed arc connecting a place to a transition is called an input arc. Conversely, an output arc connects a transition to a place. Arcs have a positive integer number called multiplicity associated with them, with the default multiplicity associated with an arc being 1. Places can contain tokens that move from one place to another through transitions. A transition is enabled when each of the places connected to it by its input arcs have at least the number of tokens equal to the multiplicity of those arcs. When an enabled transition fires, a number of tokens equal to the input arc multiplicity is removed from each one of the corresponding input places and a number of tokens equal to the output arc multiplicity is deposited in each one of the corresponding output places. The state of a Petri net with p places is represented by a vector (m_{1}, m_{2}, …, m_{p}), where m_{i} is the number of tokens in place i. The state of a Petri net is often referred to as its marking. When a Petri net is specified, it can be made to start at a particular marking called the initial marking. Subsequently, the net evolves by the successive enabling and firing of transitions, which causes the tokens to flow among places.

Stochastic Petri nets [13] extend Petri nets by allowing timed transitions that have exponentially distributed firing times. Generalized stochastic Petri nets (GSPNs) [13] also allow immediate transitions, which fire instantaneously. GSPNs include an inhibitor arc, which can also have a multiplicity associated with it.

An inhibitor arc inhibits the transition it is connected to if the place it is connected to at its other end has a number of tokens equal to at least its multiplicity. The default multiplicity is 1. A GSPN marking with at least one immediate transition enabled is called a vanishing marking, and a marking with no immediate transitions enabled is called a tangible marking.

Stochastic reward nets (SRNs) extend GSPNs further by allowing the association of a reward rate to each tangible marking. The SRN models allow the concise specification of various reward functions. To extend the power of specification, SRN includes specification of enabling (or guard) functions for each transition. The transition is enabled only if the enabling function returns “1.” SRNs also allow marking dependent arc multiplicities and enabling functions. Another feature of SRNs is the provision of priorities and probabilities to determine which of a set of simultaneously enabled transitions will fire first: the transition with the highest priority is fired first. If the competing transitions have the same priority the one to fire first is chosen probabilistically.

In a graphical representation of a SRN, a place is represented as a circle, n tokens in a place are represented by n dots or the number n within the place, immediate transitions are represented by thin lines, and exponentially distributed timed transitions are represented by empty rectangles. An inhibitor arc is represented by a circle instead of an arrow at the terminating end. An arc with multiplicity m is represented by a “|m” on the arc, and an arc with a marking dependent multiplicity function is indicated by a “N” or an inverted “N” in it.

Stochastic reward nets have been extensively used for performance, reliability and performability analysis of a variety of systems [14, 5, 6, 17, 7, 11]. The work closest to our work is reported by Ramani et al. [14], where SRNs are used for the performance analysis of the CORBA event service. The CORBA event service is yet another pattern that provides publish/subscribe services.

4 Performability Model of the Reactor

In this section we describe the process of constructing a SRN model for the reactor pattern. Towards this end, we first describe the characteristics of the reactor pattern and the relevant performance measures. A SRN model of the reactor pattern is then presented along with a discussion of how the performance measures can be obtained by assigning reward rates at the net level. We conclude the section with a discussion of possible extensions to the SRN model.

4.1 Characteristics of the Reactor Pattern

In our performability model of the reactor, we consider a single-threaded, select-based implementation of the reactor pattern with the following characteristics, as shown in Figure 4:

Figure 4: Characteristics of the Reactor

• The reactor receives two types of input events with one event handler for each type of event registered with the reactor.

• Each event type has a separate queue, which holds the incoming events of that type. The buffer capacity for the queue of type #1 events is denoted N_{1} and of type #2 events is denoted N_{2}.

• Event arrivals for both types of events follow a Poisson distribution with rates λ_{1} and λ_{2}, while the service times of the events are exponentially distributed with rates μ_{1} and μ_{2}.

• In a snapshot, when event handles corresponding to both event types are enabled, the event handle corresponding to type #1 event is serviced with a priority over event handle of type #2 event.

• The failures in the reactor are assumed to occur only in the event handlers (e.g., due to memory corruption), in which case the event is simply purged from the system. The failure rates when handling events of type #1 and type #2 are γ_{1} and γ_{2}, respectively. Other kinds of failures not considered here will cause the entire application to fail due to the single thread model.

4.2 Desired Performance Metrics

The following performance metrics are of interest for each one of the event types in the reactor pattern described in Section 4.1:

• Expected throughput – which provides an estimate of the number of events that can be processed by the single threaded event demultiplexing framework. These estimates are important for many applications, such as telecommunications call processing.

• Expected queue length – which provides an estimate of the queuing for each of the event handler queues. These estimates are important to develop appropriate scheduling policies for applications with real-time requirements.

• Expected total number of events – which provides an estimate of the total number of events in a system. These estimates are also tied to scheduling decisions. In addition, these estimates will determine the right levels of resource provisioning required to sustain the system demands.

• Probability of event loss – which indicates how many events will have to be discarded due to lack of buffer space. These estimates are important particularly for safety-critical systems, which cannot afford to lose events. These also provide an estimate on the desired levels of resource provisioning.

4.3 SRN Model of the Reactor Pattern

Description of the net: Figure 5 shows the SRN model for the reactor pattern with the characteristics described in Section 4.1. The top net models the arrival, queuing, service and failures of the two types of events. Transitions A1 and A2 represent the arrival of the events of type #1 and #2, respectively. Places B1 and B2 represent the queue for the two types of events. Transitions Sn1 and Sn2 are immediate transitions that are enabled when a snapshot is taken. Places S1 and S2 represent the enabled event handles of the two types of events, whereas transitions Sr1 and Sr2 represent the execution of the enabled event handlers of the two types of events. Transitions T F ail1 and T F ail2 represent the failures that may occur during the service of the enabled event handles of the two types of events. An inhibitor arc from place B1 to transition

Figure 5: SRN Model of the Reactor Pattern

A1 with multiplicity N1 prevents the firing of transition A1 when there are N1 tokens in place B1. The presence of N1 tokens in place B1 indicates that the buffer space to hold the incoming input events of the first type is full, and no additional incoming events can be accepted. The inhibitor arc from place B2 to transition A2 achieves the same purpose for type #2 events. The inhibitor arcs from place S1 to transition Sr2 and T F ail2 prevent the firing of transitions of Sr2 and T F ail2 when there is a token in place S1. This models prioritized service for the events of type #1 over events of type #2.

The bottom net models the process of taking successive snapshots. Transition Sn1 is enabled when there is a token in place StSnpSht, at least one token in place B1, and no tokens in place S1. Similarly, transition Sn2 is enabled when there is a token in place StSnpSht, at least one token in place B2, and no tokens in place S2. Transition T SrvSnpSht is enabled when there is a token in either one of the places S1 and S2, and the firing of this transition deposits a token in place SnpShtInP rog. Transitions Sn1 and Sn2 are assigned the same priority, and the priority of Sn1 and Sn2 is higher than the priority assigned to transition T SrvSnpSht.

The presence of a token in the place SnpShtInP rog indicates that the event handles that were enabled in the current snapshot are being serviced. After these event handles complete execution, the current snapshot is complete and it is time to take another snapshot. This is accomplished by enabling the transition T EndSnpSht. Transition T EndSnpSht is enabled when there are no tokens in both places S1 and S2. Firing of the transition T EndSnpSht deposits a token in place StSnpSht, indicating that the service of the enabled handles in the present snapshot is complete, which marks the initiation of the next snapshot. Table 1 summarizes the enabling/guard functions for the transitions in the net.

Table 1: Guard functions

Transition  Guard function
Sn1  ((#StSnpShot == 1)&&(#B1 >= 1)&&(#S1 == 0))?1 : 0
Sn2  ((#StSnpShot == 1)&&(#B2 >= 1)&&(#S2 == 0))?1 : 0
T SrvSnpSht  ((#S1 == 1)||(#S2 == 1))?1 : 0
T EndSnpSht  ((#S1 == 0&&(#S2 == 0))?1 : 0

Dynamic evolution of the net: The process of taking a single snapshot is represented by the SRN model presented in Figure 5 as follows. We consider a scenario where there is one token in each one of the places B1 and B2, no tokens in places S1 and S2, and a token in place StSnpSht. In this scenario, transitions Sn1 and Sn2 are enabled. Because both these transitions are assigned the same priority, any one of these transitions can fire first. Also, since these transitions are immediate, their firing occurs instantaneously. Without loss of generality, we assume that transition Sn1 fires before Sn2, and this deposits a token in place S1.

When a token is deposited in place S1, transition T SrvSnpSht is enabled. In addition, transition Sn2 is already enabled. If transition T SrvSnpSht were to fire before transition Sn2, it would disable transition Sn2, and prevent the handle corresponding to the second event type from being enabled. In order to prevent transition T SrvSnpSht from firing before transition Sn2, transition T SrvSnpSht is assigned a lower priority than transition Sn2. Because transitions Sn1 and Sn2 have the same priority, this also implies that transition T SrvSnpSht has a lower priority than transition Sn1. This ensures that in a given snapshot, event handles corresponding to each event type are enabled, before the service of any enabled event handle begins, when there is at least one event in the queue.

After both event handles are enabled, transition T SrvSnpSht fires and deposits a token in place SnpShtInP rog. The presence of a token in place SnpShtInP rog indicates that the event handles that were enabled in the current snapshot are being serviced. The event handle corresponding to a type #1 event is serviced first, which causes transition Sr1 to fire resulting in the removal of the token from place S1. If transition T F ail1 fires prior to the firing of transition Sr1, it indicates that a failure occurred before the event handle could complete execution. The firing of transition T F ail1 also removes the token from place S1. Subsequently, transition Sr2 fires and the event handle corresponding to the event of type #2 is serviced. This causes the removal of the token from place S2. Transition T F ail2 plays the same role as T F ail1 in the service of type #2 events. After both events are serviced and there are no tokens in places S1 and S2, transition T EndSnpSht fires, which marks the end of the present snapshot and the beginning of the next.

Assignment of reward rates: The performance measures described in Section 4.2 can be computed by assigning reward rates at the net level as summarized in Table 2. The throughputs T_{1} and T_{2} are given by the rate at which transitions Sr1 and Sr2 fire. The queue lengths Q_{1} and Q_{2} are given by the number of tokens in places B1 and B2, respectively. The total number of events E_{1} is given by the sum of the number of tokens in places B1 and S1. Similarly, the total number of events E_{2} is given by the sum of the number of tokens in places B2 and S2. The loss probability L_{1} is given by the probability of N1 tokens in place B1. Similarly, the loss probability L_{2} is given by the probability of N2 tokens in place B2.

Table 2: Reward assignments to obtain performance measures

Performance metric  Notation  Reward rate
Throughput of event type #1  T_{1}  return rate(Sr1)
Throughput of event type #2  T_{2}  return rate(Sr2)
Queue length of event type #1  Q_{1}  return (#B1)
Queue length of event type #2  Q_{2}  return (#B2)
Loss probability of event type #1  L_{1}  return (#B1 == N1?1 : 0)
Loss probability of event type #2  L_{2}  return (#B2 == N2?1 : 0)
Total number of events of type #1  E_{1}  return(#B1 + #S1)
Total number of events of type #2  E_{2}  return(#B2 + #S2)

The SRN model can be solved easily by tools such as the Stochastic Petri Net Package (SPNP) [4] to obtain the expected performance metrics for different values of the parameters.

4.4 Model Variations

In the model of the reactor pattern described above, the arrival, service and failure distributions are assumed to be exponential. For certain types of applications, this assumption may not hold. For example, for safetycritical applications, events may occur at regular intervals, in which case the arrival process is deterministic. In addition to the deterministic distribution, the arrival, service and failure processes may also follow any other non-exponential or general distribution. There are two ways to consider non-exponential distributions in the SRN model. In the first method, a non-exponential distribution can be approximated using a phasetype approximation [13], and the resulting SRN model can then be solved using SPNP. In the second method, the model can be simulated using discrete-event simulation incorporated in SPNP [4].

5 Performability Analysis of Virtual Router

In this section we illustrate how the SRN model of the reactor pattern is used for the performability analysis of a Virtual Private Network (VPN) service provided by a Virtual Router (VR). The main purpose of this exercise is not to draw any conclusions about specific parameter values, but to demonstrate how reasonable values of the parameters can be systematically determined through careful analysis at the time of designing a service.

We consider a scenario where a VR is used to provide VPN services to two organizations, with each organization having a customer edge (CE) router connected to the VR. The employees of each organization issue VPN set up and tear down service requests to the VR via CEs. Also, the VR offers a differentiated level of service, with organization #1 receiving prioritized service over organization #2. From the point of view of the employees of the organizations, it is necessary that the service requests be handled in a reasonable amount of time. Also, the probability of denying the service requests should be minimal. From the point of view of the VPN service provider, the rate at which the service requests are processed or the throughput is of interest, since this will determine the revenue generated for the provider.

In order to implement the VPN service, a reactor pattern with the characteristics described in Section 4.1 can be used to demultiplex the events. The SRN model of the reactor pattern can thus be used for the performability analysis of the VPN service provided by the VR. In order to use the SRN model, we designate the requests originating from organization #1 as events of type #1 and requests originating from organization #2 as events of type #2.

In the early stages of application development lifecycle, it is necessary to analyze the impact of design choices and configurations on the performability measures. Also, in these stages, it is rarely the case that the values of the input parameters can be estimated with certainty, which makes it imperative to analyze the sensitivity of the performability measures to the variations in the input parameters. Sensitivity analysis will enable the provider to determine the regions of operation during which service performance is acceptable. In the subsequent subsections we demonstrate how the SRN model can be used to explore alternative design configurations, as well as to facilitate sensitivity analysis.

5.1 Impact of Buffer Space

The buffer space available to hold the incoming events of each type is a configuration parameter of the reactor pattern and the VPN service that uses the pattern. This choice will have a direct impact on all the performability metrics. Most importantly, from the employees’ perspective, the buffer space will influence the probability of denying the service requests.

We analyze the impact of the buffer capacities on the performability measures. The values of the remaining parameters (except for the buffer capacities) are reported in Table 3. We consider two values of buffer capacities N_{1} and N_{2}. In the first case, the buffer capacity is set to 1 for both types of events, whereas in the second case the buffer capacity of both types of events is set to 5. The performability metrics for both these cases are summarized in Table 4. Because the values of the parameters of the service requests from organization #1 (λ_{1}, μ_{1} and N_{1}) are the same as the values of the parameters for the service requests from organization #2 (λ_{2}, μ_{2}, and N_{2}), the throughputs, queue lengths, and the loss probabilities are the same for both types of service requests for each one of the buffer capacities as indicated in Table 4. It can be observed that the loss probabilities are significantly higher when the buffer capacity is 1 compared to the case when the buffer space is 5. Also, due to the higher loss probability, the throughput is slightly lower when the buffer capacity is 1 than when the buffer capacity is 5.

For both buffer capacities, the total number of service requests from organization #2, denoted E_{2}, is slightly higher than the total number of requests from organization #1, denoted E_{1}. Because the requests from organization #1 are provided prioritized service over the requests from organization #2, on an average it takes longer to service a request from organization #2 than it takes to service a request from organization #1. This results in a higher total number of requests from organization #2 than the total number of requests from organization #1. This may result in a higher response time for service requests from organization #2 as compared with the service requests from organization #1. The reward rates to obtain the response times can be obtained using the tagged customer approach [10] and is a topic of our future research.

Table 3: Parameter values

Event type Arrival rate Service rate Failure rate
#1  λ_{1} = 0.400/sec. μ_{1} = 2.000/sec. γ_{1} = 0.02/sec.
#2  λ_{2} = 0.400/sec. μ_{2} = 2.000/sec. γ_{2} = 0.02/sec.

Table 4: Impact of buffer capacity on performability measures

Performability measure  Buffer space
N_{1} = 1, N_{2} = 1 N_{1} = 5, N_{2} = 5
T_{1}  0.37/sec.  0.39/sec.
T_{2}  0.37/sec.  0.39/sec.
Q_{1}  0.06  0.12
Q_{2}  0.06  0.12
E_{1}  0.25  0.31
E_{2}  0.27  0.34
L_{1}  0.06  0.00024
L_{2}  0.06  0.00024

5.2 Impact of Service Rates

Another design parameter that will impact the service performance is the service time of the event handlers. Obviously, a faster rate of service will improve performance, but from the provider’s perspective, increasing the service rate may require higher levels of resources thereby increasing the cost. Therefore, it is necessary to determine what service rate would be “good enough” to provide acceptable service performance. This can be accomplished by analyzing the sensitivity of the performability metrics with respect to the service rates, namely, μ_{1} and μ_{2}.

The results reported in Section 5.1 indicate that the loss probability is significantly lower when the buffer space is 5 as compared to the loss probability when the buffer space is 1. As a result, for the purpose of sensitivity analysis with respect to μ_{1} and μ_{2}, we set the buffer capacity for both service requests to be 5. We vary the service rates μ_{1} and μ_{2} in the range of 0.4/sec. to 2.0/sec. roughly in steps of 0.025, one at a time, to obtain the expected performance measures by solving the SRN model shown in Figure 5. The remaining parameters are held at the values reported in Table 3.

The plots in the left column of Figure 6 show the variation of the performability measures with respect to μ_{1}, while the plots in the right column of Figure 6 show the variation with respect to μ_{2}. The topmost plot in the left column shows the variation of throughputs of service requests from organizations #1 and #2 with respect to μ_{1}. The figure indicates that as μ_{1} decreases, the throughputs of requests from both organizations decrease; however, the magnitude of decrease in the throughput of requests from organization #1 is higher than the magnitude of decrease in the throughput of the requests from organization #2. The second and the fourth plots in the same column show the variation of the total number of requests and the queue length for requests from both organizations as a function of μ_{1}. It can be observed that both the total number of requests and the queue length increase as μ_{1} decreases, and the magnitude of increase for service requests from organization #1 is higher than the magnitude of increase for requests from organization #2. Similar trends can be observed in the variation of the loss probabilities in the third plot.

It can be noted that as μ_{1} decreases, the performability measures degrade (loss probability, queue length and total number of events increases, and throughput decreases). Also, as μ_{1} decreases below 0.8/sec., the performability measures deteriorate rapidly. With decreasing μ_{1}, the time taken to service a request from organization #1 increases due to the additional time taken to complete each snapshot. As a result, indirectly, this also increases the time taken to service a request from organization #2 in each snapshot. Thus, the performance of requests from both organizations are adversely impacted, even though only the service time for the requests from only one of the organizations increases. The variation of the performability measures with respect to μ_{2} shows the same trend, with the role of event types reversed.

5.3 Impact of Request Arrival Rates

The arrival rates of service requests, namely, λ_{1} and λ_{2}, constitute the input parameters. In this section we analyze the the sensitivity of the performability measures to these input parameters.

Based on the results and analysis described in Section 5.1 and Section 5.2, we set N_{1} and N_{2} to 5, and we set μ_{1} and μ_{2} to 2.00/sec for sensitivity analysis with respect to λ_{1} and λ_{2}. The parameters γ_{1} and γ_{2} were held at the values reported in Table 3. The parameters λ_{1} and λ_{2} were varied one at a time in the range of 0.4/sec to 2.0/sec. roughly in steps of 0.025 to obtain the expected performability measures by solving the SRN model shown in Figure 5.

Figure 7 shows the performability measures as a function of λ_{1} and λ_{2}. The plots in the left column show the variation of the performability measures with respect to λ_{1}, whereas the plots in the right column show the variation of the performability measures with respect to λ_{2}. Referring to the topmost figure in the left

Figure 6: Sensitivity of performability measures to service rates μ_{1} and μ_{2}

column, it can be observed that initially, the throughput of service requests from organization #1 is nearly the same as the arrival rate of the requests, indicating that the requests are serviced at the same rate at which they arrive. However, as λ_{1} increases, the throughput starts lagging the arrival rate, which indicates that the service rate is not sufficiently high to process the requests at the rate at which they arrive. This may cause the queue for requests from organization #1 to operate at full capacity for an extended period of time, which

Figure 7: Sensitivity of performability measures to arrival rates λ_{1} and λ_{2}

results in a rejection of the incoming requests from organization #1.

It can be observed that a decrease in the rate at which the throughput increases is marked by an increase in the loss probability of the requests (as shown in the third plot in the left column) and an increase in the queue length (as shown in the fourth plot in the left column) in Figure 7. The left plot in the second row represents the total number of service requests from each organization as a function of λ_{1}. The plot indicates that the total number of requests from organization #2 in the system increases as λ_{1} increases. When λ_{1} increases, the probability of having to service a request from organization #1 prior to servicing a request from organization #2 event in a given snapshot increases. Because requests from organization #1 have priority over requests from organization #2, requests from organization #2 tend to reside longer in the system as λ_{1} increases. Thus, although the throughput of requests from organization #2 is unchanged with respect to λ_{1}, the response time of the requests from organization #2 may increase. The plots in the right column of Figure 7 indicate that similar trends can be observed in the performability measures with respect to λ_{2}, except that the roles of the two types of requests are reversed.

6 Conclusion and Future Research

In this paper we presented a performability model of the reactor pattern which codifies the event demultiplexing and dispatching capabilities that lie at the heart of event-driven software applications. The model is based on the well-established Stochastic Reward Net (SRN) modeling paradigm. It considers the failures of the application in order to provide realistic performance estimates. We demonstrate the use of the model for the performability analysis of a VPN service provided by a Virtual Router. Since the reactor pattern is central to the event-driven software applications, the model proposed in this paper would enable design-time performability analysis of these applications.

Our future research involves identifying widely used patterns similar to the reactor pattern, and developing performability models of these patterns. Developing strategies to compose models of several patterns, and mirroring their use in software systems is also a topic of future research.

References

[1] A. Nagarajan (editor). Generic Requirements for Provider Provisioned Virtual Private Network (PPVPN). IETF Network Working Group Request for Comments, RFC 3809, pages 1–25, June 2004.

[2] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA, 1995.

[3] D. Garlan and M. Shaw. Advances in Software Engineering and Knowledge Engineering, Volume 1, edited by V. Ambriola and G. Torotora, chapter An Introduction to Software Architecture. World Scientific Publishing Company, New Jersey, 1993.

[4] C. Hirel, B. Tuffin, and K. S. Trivedi. SPNP: Stochastic Petri Nets. Version 6.0. Lecture Notes in Computer Science 1786, 2000.

[5] O. Ibe, A. Sathaye, R. Howe, and K. S. Trivedi. Stochastic Petri net modeling of VAXCluster availability. In Proc. of Third International Workshop on Petri Nets and Performance Models, pages 142–151, Kyoto, Japan, 1989.

[6] O. Ibe and K. S. Trivedi. Stochastic Petri net models of polling systems. IEEE Journal on Selected Areas in Communications, 8(9):1649–1657, December 1990.

[7] O. Ibe and K. S. Trivedi. Stochastic Petri net analysis of finite–population queueing systems. Queueing Systems: Theory and Applications, 8(2):111–128, 1991.

[8] Paul Knight, Hamid Ould-Brahim, and Bryan Gleeson. Network based VPN Architecture using Virtual Routers. IETF Network Working Group Internet Draft, draft-ietf-l3vpn-vpn-vr-02.txt, pages 1–21, April 2004.

[9] Jane W. S. Liu. Real-Time Systems. Prentice Hall, New Jersey, 2000.

[10] B. Melamed and M. Yadin. Randomization procedures in the computation of cumulative-timed distributions over discrete-state markov process. Operations Research, 32(4):926–944, July-August 1984.

[11] J. Muppala, G. Ciardo, and K. S. Trivedi. Stochastic reward nets for reliability prediction. Communications in Reliability, Maintainability and Serviceability: An International Journal Published by SAE Internationa, 1(2):9– 20, July 1994.

[12] J. L. Peterson. Petri Net Theory and the Modeling of Systems. Prentice-Hall, 1981.

[13] A. Puliafito, M. Telek, and K. S. Trivedi. The evolution of stochastic Petri nets. In Proc. of World Congress on Systems Simulation, pages 3–15, Singapore, September 1997.

[14] S. Ramani, K. S. Trivedi, and B. Dasarathy. Performance analysis of the CORBA event service using stochastic reward nets. In Proc. of the 19th IEEE Symposium on Reliable Distributed Systems, pages 238–247, October 2000.

[15] Douglas C. Schmidt, Michael Stal, Hans Rohnert, and Frank Buschmann. Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects, Volume 2. Wiley & Sons, New York, 2000.

[16] C.U. Smith. Performance Engineering of Software Systems. Addison Wesley, 1990.

[17] H. Sun, X. Zang, and K. S. Trivedi. A stochastic reward net model for performance analysis of prioritized DQDB MAN. Computer Communications, Elsevier Science, 22(9):858–870, June 1999.

[18] K. S. Trivedi. Probability and Statistics with Reliability, Queuing and Computer Science Applications. John Wiley, 2001.