04-03-2013, 04:01 PM
Performance Investigation of an On-Line Auction System
Performance Investigation.pdf (Size: 234.64 KB / Downloads: 33)
Abstract
The standard design of on-line auction systems places most of the compu-
tational load on the server and its adjacent links, resulting in a bottleneck in
the system. In this paper, we investigate the impact, in terms of the perfor-
mance of the server and its adjacent links, of introducing active nodes into the
network. The performance study of the system is done using the stochastic
process algebra formalism PEPA.
Introduction
In this paper we investigate the interplay of two emerging technologies: active net-
works and software agents to support electronic commerce.
Active networks[1] are a compelling new initiative in networking. An active network
extends a conventional one with the ability for network switches to process
data as it is being transmitted. The processing which is to be performed can be
customised by the network user on a per-application or even per-message basis. This
innovation is a dramatic departure from traditional network design where the emphasis
is on the avoidance of examination or modication of data. Active networks
are supported by a variety of software technologies, execution environments and
node operating systems [2].
The On-line Auction System
In an on-line auction system, a server receives and processes bids from remote software
agents representing interested consumers. These semi-autonomous agents submit
bids according to a predetermined strategy together with the information that
they can ascertain from the server. The server processes bids, either accepting them or rejecting them, depending on their value. In some systems additional attributes
may be considered when comparing bids of the same or close value.
In addition to bids, bidder agents may also submit price notication requests,
asking the server to tell them the latest bidding price. Note that the bidder agents
can never be certain that they have an accurate representation of the current price
due to network latency. They can, however, be certain that their current representation
is out of date when a submitted bid, which is higher than their idea of the
\current" price, is rejected.
The PEPA models
PEPA (Performance Evaluation Process Algebra) extends classical process algebra
by associating a random variable, representing duration, with every action. These
random variables are assumed to be exponentially distributed giving a clear relationship
between the process algebra model and a Markov process.
PEPA models are described as interactions of components. Each component can
perform a set of actions: an action a 2 Act is described as a pair (; r), where
2 A is the type of the action and r 2 R+ is the parameter of the negative
exponential distribution governing its duration. Whenever a process P can perform
an action, an instance of a given probability distribution is sampled: the resulting
number species how long it will take to complete the action. A small but powerful
set of combinators is used to build up complex behaviour from simpler behaviour.
The combinators are familiar from classical process algebra: prex, choice, parallel
composition and abstraction. We explain each of the combinators informally below.
A formal operational semantics for PEPA is available in [8].
The system without active node
The PEPA model corresponding to the on-line auction system with only traditional
nodes is composed of six components. The conguration we consider is shown in
Figure 2.
The PEPA model is composed of components Server, Bidder, Node for the basic
node, CNode for the central node and TNode for the upstream one. For technical
reasons, a bidder connected to the central node is modelled using the component
BidderCN. Action types are used to ensure the correct routing within the network
model: the suxes csb and csn are used to denote messages to the server via the
upstream node and via the central node and the upstream node, respectively. The
suxes scb and scn denote messages in the reverse direction.
Experiments and Numerical Results
Through the analysis and solution of the Markov process underlying a PEPA model,
the modeller can undertake an experimental investigation of the system. The PEPA
Workbench is a suite of tools which perform the well-formedness checking of PEPA
models as well as the generation and solution of the corresponding Markov process
[9]. It detects faults such as deadlocks and cooperations which do not involve active
participants. In the most recent version, it includes support for a modal logic, allowing
behavioural requirements of a model to be formally expressed and automatically
checked [12].
In essence, the translation process which occurs within the PEPA Workbench
accepts a PEPA model as input and produces a matrix containing the Markov
process encoding of the model given. In the most straightforward translation a
state of the Markov process is associated with each syntactic term of the PEPA
model obtained by application of the structured operational semantics rules. To
solve the models presented in this paper we took advantage of a modied version
of the Workbench which automatically aggregates models, during exploration of the
state space. Using this translation one state of the Markov process is associated with
each equivalence class of states, where two states are considered equivalent if they
generate the same observable behaviour. More details of this automatic aggregation
can be found in [13].