|
|
 |
Technical Reports
Send queries to reports@cse.unsw.edu.au.
TR #
|
Title
|
Author(s) and Affiliation(s)
|
Abstract
|
| 0920 |
Ear-Phone: An End-to-End Participatory Urban Noise Mapping System |
Rajib Kumar Rana
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: rajibr@cse.unsw.edu.au
Chun Tung Chou
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: ctchou@cse.unsw.edu.au
Salill Kanhere
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: salilk@cse.unsw.edu.au
Nirupama Bulusu
Department of Computer Science
Portland State University, USA
E-mail: nbulusu@cs.pdx.edu
Wen Hu
CSIRO ICT Centre, Australia
E-mail: wen.hu@csiro.au |
A noise map facilitates monitoring of environmental noise pollution in urban
areas. It can raise citizen awareness of noise pollution levels, and aid in the
development of mitigation strategies to cope with the adverse effects. However,
state-of-the-art techniques for rendering noise maps in urban areas are expensive
and rarely updated (months or even years), as they rely on population and traffic
models rather than on real data. Participatory urban sensing can be leveraged
to create an open and inexpensive platform for rendering up-to-date noise maps.
In this paper, we present the design, implementation and performance evaluation
of an end-to-end participatory urban noise mapping system called Ear-
Phone. Ear-Phone, for the first time, leverages Compressive Sensing to address
the fundamental problem of recovering the noise map from incomplete
and random samples obtained by crowdsourcing data collection. Ear-Phone,
implemented on Nokia N95 and HP iPAQ mobile devices, also addresses the
challenge of collecting accurate noise pollution readings at a mobile device. We
evaluate Ear-Phone with extensive simulations and outdoor experiments, that
demonstrate that it is a feasible platform to assess noise pollution with reasonable
system resource consumption at mobile devices and high reconstruction
accuracy of the noise map. |
| 0919 |
Spreadsheet-based Complex Data Transformation |
Regis Saint-Paul
CREATE-NET, Italy
regis.saint-paul@create-net.org
Hung Vu
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: vthung@cse.unsw.edu.au
Ghazi Al-Naymat
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: ghazi@cse.unsw.edu.au
Boualem Benatallah
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: boualem@cse.unsw.edu.au |
Most solutions to data transformation rely on schema mapping to transform a source
instance to the target format. However, there are many cases in which the schema of
the source instance is unknown and transformation is performed directly from the
source instance to the target schema. Spreadsheets are routinely used by millions of
users as an all-purpose data management tool. It is now increasingly necessary for external
applications to consume spreadsheet data. In this paper, we investigate the problem of
transforming spreadsheets to structured formats required by these applications.
We propose a novel approach in which transformation logic is embedded into a familiar
spreadsheet-based mapping language, instead of the source document. As a result, it avoids
cluttering the source document and turns out to be helpful when multiple schemas are
argeted. The language also supports the generalization of mappings from instance-level
to template-level. We implement a prototype and demonstrate the benefits of our approach
ia experiments in real-world contexts, namely end-user visualization and medical data transfer. |
| 0918 |
OpenPEX: An Open Provisioning and EXecution System for Virtual Machines |
Srikumar Venugopal
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: srikumarv@cse.unsw.edu.au
James Broberg
Department of Computer Science and Software Engineering,
The University of Melbourne,
VIC 3010, Australia
E-mail: brobergj@csse.unimelb.edu.au
Rajkumar Buyya
Department of Computer Science and Software Engineering,
The University of Melbourne,
VIC 3010, Australia
E-mail: raj@csse.unimelb.edu.au |
Virtual machines (VMs) have become capable enough to emulate full-featured
physical machines in all aspects. Therefore, they have become the foundation not
only for flexible data center infrastructure but also for commercial Infrastructure-as-a-Service (IaaS) solutions. However, current providers of virtual infrastructure offer simple mechanisms through which users can ask for immediate allocation of VMs. More sophisticated economic and allocation mechanisms are required so that users can plan ahead and IaaS providers can
improve their revenue. This paper introduces OpenPEX, a system that allows users to provision resources ahead of time through advance reservations. OpenPEX also incorporates a bilateral negotiation protocol that allows users and providers to come to an agreement by exchanging offers and counter-offers. These functions are made available to users through a web portal and a REST-based Web service interface. |
| 0917 |
Performance of Multi-hop Whisper Cognitive Radio Networks |
Quanjun Chen, Chun Tung Chou, Salil S. Kanhere, Wei Zhang(*), Sanjay K. Jha
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: {quanc, ctchou, salilk, sanjay}@cse.unsw.edu.au
(*)School of Electrical Engineering and Telecommunications,
The University of New South Wales, Sydney, Australia,
Email: w.zhang@unsw.edu.au |
In 2003, Federal Communications Commission (FCC) has released a new spectrum policy
called ``Interference Temperature model" to improve the channel access opportunities
of secondary users. Under this model, the secondary users are allowed to access the
licensed spectrum simultaneously with the primary users provided that the
interference at the primary receiver meets a certain threshold. We refer the
Cognitive Radio Networks that employs this model as ``Whisper CRNs" (since secondary
users have to use smaller transmission power to satisfy the interference constraint).
In this work, we systematically analyze the performance of whisper CRNs and compare
it with the traditional CRNs, where the secondary users are not allowed to transmit
when primary users are busy. We aim to answer the fundamental question: what is the
performance trade-off by switching to whisper CRNs from traditional CRNs. Based on
the performance analysis, we also propose an efficient channel assignment scheme that
has a small channel switching overhead. The results show that whisper CRNs can
improve the connectivity and end-to-end throughput of secondary users considerably
(by more than two times in some scenarios) but at the cost of increasing end-to-end
delay. We also show that the node density of secondary users has a significant impact
on the performance of whisper CRNs. |
| 0916 |
Characterizing Human Effort in Wireless Voice Over IP |
Jahan A. Hassan
School of Computer Science and Engineering
University of New South Wales
Kensington, Sydney 2052, Australia
E-mail: jahan@cse.unsw.edu.au
Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales
Kensington, Sydney 2052, Australia
E-mail: mahbub@cse.unsw.edu.au
Sajal K. Das
Department of Computer Science and Engineering
University Texas at Arlington
P.O. Box 19015
Arlington, TX 76019, USA |
Skype Voice Over IP (VoIP) traces from an experimental WiFi network were analyzed to detect
and characterize user efforts that go into these calls. Our analysis shows that
users have a very low tolerance threshold when it comes to putting efforts for getting the
conversation going (they prefer rather effort-less conversation). A wireless VoIP session is
highly likely to be abandoned prematurely by the user if the effort threshold is exceeded
during the call. Our results also suggest that after exceeding the effort threshold, users
are likely to spend quite a bit of time in the call before finally abandoning it. These
effort patterns are found to be consistent across multiple users, with the actual value of
the effort threshold being sensitive to the user. An important outcome is that it is possible
to reliably generate warnings for calls that are going to face premature ending by simply
monitoring the number of times the user has put efforts into the call. Besides reliability,
these warnings can be generated well in advance giving plenty of time to network controllers
for possible repair of the wireless connection and avoidance of premature call ending. Using
the effort data captured from our experimental network, we conduct discrete event simulations
of a WiFi VoIP network to evaluate the effectiveness of dynamic resource allocation in
addressing such warnings. The experiments show that resource allocation schemes which are
capable of exploiting the long warning lead times of effort-based predictions, can find
additional resources with a high probability. |
| 0915 |
Efficient computation of robust average in wireless sensor networks using compressive sensing |
Chun Tung Chou
School of Computer Science and Engineering,
University of New South Wales, Australia
ctchou@cse.unsw.edu.au
Aleksandar Ignjatovic
School of Computer Science and Engineering,
University of New South Wales, Australia
ignjat@cse.unsw.edu.au
Wen Hu
Autonomous Systems Laboratory,
CSIRO ICT Centre, Brisbane, Australia
Wen.Hu@csiro.au |
Wireless sensor networks (WSNs) enable the collection of physical measurements over a large geographic area.
It is often the case that we are interested in computing and tracking the spatial-average of the sensor
measurements over a region of the WSN. Unfortunately, the standard average operation is not robust because it
is highly susceptible to sensor faults (e.g. offset, stuck-at errors etc.) and variation of sensor
measurement noises. In this paper, we propose a method to compute a robust average of sensor measurements,
which appropriately takes sensor faults and sensor noise into consideration, in a bandwidth- and
computational-efficient manner. At the same time, the proposed method can determine which sensors are likely
to be faulty. Our method achieves bandwidth efficiency by exploiting compressive sensing. Instead of sending
a block of sensor readings to the data fusion centre, each sensor performs random projections (as in
compressive sensing) on the data block and sends the results of the projections (which we will refer to as
the compressed data) to the data fusion centre. At the data fusion centre, we achieve computational
efficiency by working directly with the compressed data, whose dimension is only a fraction of that of the
original block of sensor data. In other words, our proposed method will work on the compressed data without
decompressing them. By using the compressed data, our proposed method will determine which sensors are likely
to be faulty as well as a robust average of the compressed data, which, after decompression (or compressive
sensing reconstruction), will yield an approximation of the robust average of the original sensor readings.
This means that the data fusion centre will only need to perform decompression once in order to obtain the
robust average (rather than decompressing all the compressed data from all the sensors), therefore achieving
computational efficiency. We apply our proposed method to the data collected from a number of WSN deployments
to demonstrate its efficiency and accuracy. |
| 0914 |
SuSeSim: A Fast Simulation Strategy to Find Optimal L1 Cache Configuration for Embedded Systems |
Mohammad Shihabul Haque
School of Computer Science and Engineering,
University of New South Wales, Australia
mhaque@cse.unsw.edu.au
Andhi Janapsatya
School of Computer Science and Engineering,
University of New South Wales, Australia
andhij@cse.unsw.edu.au
Sri Parameswaran
School of Computer Science and Engineering,
University of New South Wales, Australia
sridevan@cse.unsw.edu.au |
Simulation of an application is a popular and reliable approach to find the op-
timal con¯guration of L1 cache memory for an application specific embedded
system processor. However, long simulation time is one of the main disadvan-
tages of simulation based approaches. In this paper, we propose a new and fast
simulation method, Super Set Simulator (SuSeSim). While previous methods
use Top-Down searching strategy, SuSeSim utilizes a Bottom-Up search strat-
egy along with a new elaborate data structure to reduce the search space to
determine a cache hit or miss. SuSeSim can simulate hundreds of cache config-
urations simultaneously by reading an application's memory request trace just
once. Total number of cache hits and misses are accurately recorded. Depending
on different cache block sizes and benchmark applications, SuSeSim can reduce
the number of tags to be checked by up to 43% compared to the existing fastest
simulation approach (the CRCB algorithm). With the help of a faster search
and an easy to maintain data structure, SuSeSim can be up to 94% faster in
simulating memory requests compared to the CRCB algorithm. |
| 0913 |
Phylogeny, Genealogy, and the Linnaean Hierarchy: Formal Proofs |
Rex Kwok
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: rkwok@cse.unsw.edu.au |
Phylogenetic terms (monophyly, polyphyly, and paraphyly) were first
used in the context of a phylogenetic tree. However, the only
possible source for a phylogeny is a genealogy. This paper presents
formal definitions for phylogenetic terms in a genealogical context
and shows that their properties match their intuitive meanings.
Moreover, by presenting the definitions in a genealogical context, a firm
connection between genealogy and phylogeny is established. To support
the correctness of the definitions, results will show that they satisfy
the appropriate properties in the context of a phylogenetic tree.
Ancestors in a phylogenetic tree are viewed as theoretical entities since no
means exist for proving ancestral relationships. As such,
groups of terminal species are often considered. This will impact on
phylogenetic concepts. Results will be presented showing that
monophyly and polyphyly have reasonable interpretations in this
context while the notion of paraphyly becomes degenerate.
The vigorous debate about whether biological taxa should be
monophyletic will also be addressed. Results will be presented
showing why the monophyletic condition will make a Linnaean classification
entirely monotypic. |
| 0912 |
Safety Assurance and Rescue Communication Systems in High-Stress Environments - A Mining Case Study |
Prasant Misra
School of Computer Science and Engineering
The University of New South Wales
NSW 2052, Australia
E-mail: pkmisra@cse.unsw.edu.au
Salil Kanhere
School of Computer Science and Engineering
The University of New South Wales
NSW 2052, Australia
E-mail: salilk@cse.unsw.edu.au
Diet Ostry
CSIRO, Australia
E-mail: Diet.Ostry@csiro.au
Sanjay Jha
School of Computer Science and Engineering
The University of New South Wales
NSW 2052, Australia
E-mail: sanjay@cse.unsw.edu.au |
Effective communication is critical for response and rescue operations; however,the capricious behavior of communication devices in high-stress environments
is a significant obstacle to effectiveness. High-stress environments in which disaster response and recovery operations are needed include natural calamities
such as earthquakes, tsunamis, hurricanes, tornadoes, fires, floods/flash floods in urban areas; salvage, search and rescue operations in underwater, urban war
zones, mountainous terrain, avalanches, underground mine disasters, volcanic eruptions, plane crashes, high-rise building collapses, and nuclear facility malfunctions;
and deep-space communication in outer-space exploration. We have observed a correlation between the channel characteristics that effect the performance
of the communication devices across these extreme environments. The contribution of this article is three-fold. First, it generates a list of characteristics
that affect communication in all high-stress environments and then evaluates it with respect to the underground mine environment. Second, it discusses current
underground mine communication techniques and identifies the potential problems. Third, it explores the design of a wireless sensor network (WSN)
based communication and location sensing system that could potentially meet the current challenges. Finally, we discuss some preliminary results of an empirical
study of the wireless communication characteristics of off-the-shelf MicaZ wireless sensor nodes in an underground mine in Parkes, NSW, Australia. |
| 0911 |
Synthesis of Application Specific Heterogeneous Pipelined Multiprocessor Systems |
Haris Javaid
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: harisj@cse.unsw.edu.au
Sri Parameswaran
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sridevan@cse.unsw.edu.au |
This paper describes a rapid design methodology to create a pipeline of processers to execute
streaming applications. The methodology has two separate phases. The first phase uses a heuristic to
rapidly search through a large number of processor configurations (configurations differ by the base
processor, the additional instructions and cache sizes) to find the near Pareto front. The second
phase utilizes either the above heuristic or an ILP (Integer Linear Programming) formulation to
search a smaller design space to find an appropriate final implementation. By the utilization of the
fast heuristic with differing runtime constraints in the first phase, we rapidly find the near
Pareto front. The second phase provides either an optimal or a near optimal solution. Both the ILP
formulation and the heuristic find a system with the smallest area, within a designer specified
runtime constraint. The system has efficiently explored design spaces with over 10^12 design points.
We integrated this design methodology into a commercial design flow and evaluated our approach with
different benchmarks (JPEG Encoder, JPEG Decoder and MP3 Encoder). For each benchmark, the near
Pareto front was found in a few hours using the heuristic (took several days for the ILP). The
results show that the average area error of the heuristic is within 2.5% of the optimal design
points (obtained using ILP) for all benchmarks. |
| 0910 |
Underground Mine Communication and Tracking Systems : A Survey |
Prasant Misra
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: pkmisra@cse.unsw.edu.au
Diet Ostry
CSIRO, Australia
E-mail: Diet.Ostry@csiro.au
Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sanjay@cse.unsw.edu.au |
This article presents a survey of the state-of-the art underground mine communication
and tracking systems. Underground mines are extensive labyrinths. They employ hundreds
of mining personnel working at any point of time under extreme conditions. To ensure
the safety of workers and perform co-ordination of tasks, a communication and tracking
system is one of the more important infrastructures that needs to be deployed and is
expected to deliver satisfactory performance in terms of communicating in routine and
rescue operations. To develop an engineering and scientific foundation, we need to
understand the underground channel characteristics along with the challenges faced by
wired and wireless communication solutions. |
| 0909 |
Cross-layer interactions in energy efficient information collection in wireless sensor
networks with adaptive compressive sensing |
Chun Tung Chou
School of Computer Science and Engineering,
University of New South Wales, Australia
ctchou@cse.unsw.edu.au
Rajib Rana
School of Computer Science and Engineering,
University of New South Wales, Australia
rajibr@cse.unsw.edu.au
Wen Hu
Autonomous Systems Laboratory,
CSIRO ICT Centre, Brisbane, Australia
Wen.Hu@csiro.au |
We consider the problem of using Wireless Sensor Networks (WSNs) to measure the
temporal-spatial field of some scalar physical quantities. Our goal is to obtain a sufficiently
accurate approximation of the temporal-spatial field with as little energy as possible. We
propose an adaptive algorithm, based on the recently developed theory of adaptive compressive
sensing, to collect information from WSNs in an energy efficient manner. The key idea of the
algorithm is to perform ``projections" iteratively to maximise the amount of information gain
per energy expenditure. We prove that this maximisation problem is NP-hard and propose a number
of heuristics to solve this problem. This maximisation problem can also be viewed as a routing
problem with a metric which is a non-linear function of the data field; therefore the problem is
cross-layer in nature, requiring information in both application and network layers. We evaluate
the performance of our proposed algorithms using data from both simulation and an outdoor WSN
testbed. The results show that our proposed algorithms are able to give a more accurate
approximation of the temporal-spatial field for a given energy expenditure. |
| 0908 |
Fixed Point Method for Voting |
Chung Tong Lee
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: ctlee@cse.unsw.edu.au
Aleksandar Ignjatovic
School of Computer Science and Engineering
University of New South Wales, and NICTA
NSW 2052, Australia
E-mail: ignjat@cse.unsw.edu.au |
Question answering (Q&A) community sites, such as the MSN QnA and Yahoo!
Answers, facilitate question answering by a community of users. However, the
quality of the answers provided by users varies. To determine the best answer, vote
counts, sometimes with extra weight put on the askers, are commonly used. This
makes the result vulnerable to tainted vote effect as opinions from "bad" voters
weight the same as those from the "good" ones. We propose a new method to
determine the best answer by the sum of voters’ reliability scores, which are calculated
based on voters’ behaviors. The more a voter can choose the best answer, the
more reliable he is and the more weight his opinion should carry. This is a circular
definition similar to the reputation score evaluation in [2]. Our method does not require
the identification of anomalous voting behavior to reduce the reliability score.
Instead, we employ the Brouwer Fixed Point Theorem [1] to show the existence
of the assignment for reliability scores which satisfy the axiomatic description of
the system. Iterative method is used for actual evaluation. To demonstrate the
robustness, simulations are designed with data that match the real-life situation,
augmented with various forms of anomalous behaviors. |
| 0907 |
LOP: A Novel SRAM-based Architecture for LOw Power Packet Classification |
XIN HE
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: xinhe@cse.unsw.edu.au
Jorgen Peddersen
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: jorgenp@cse.unsw.edu.au
Sri Parameswaran
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sridevan@cse.unsw.edu.au |
Performance of packet classification algorithms is an important area of concern in modern
networks. Algorithms for matching incoming packets from the network to pre-defined rules, have
been proposed by a number of researchers. Current software-based packet classification
techniques have low performance, so many researchers have moved their focus to new architectures
encompassing both software and hardware components. Some of the newer hardware architectures
exclusively utilize Ternary Content Addressable Memory (TCAM) to improve performance of rule
matching. However, this results in systems with very high power consumption. TCAM consumes a
high amount of power as the entire memory array is read during any given access, much of which
may not be necessary. In this paper, we propose a novel SRAM-based (named LOP) architecture
where incoming packets are compared against parts of all rules simultaneously until a single
matching rule is found for the compared bits in the packets, significantly reducing power
consumption (i.e., only a segment of the memory is compared to the incoming packet). This comes
with a penalty of time to match a single packet, but multiple packets can be compared in parallel
to improve throughput beyond the levels of TCAM approaches.
Nine different benchmarks were tested in with two classification systems, with results showing
that LOP architectures provide high lookup rates and throughput, and consume low power. Compared
with a low power commercial TCAM approach, LOP achieves power reduction of more than 60% with
equivalent throughput, and a power reduction of about 20% with high throughput (220 million
searches per second (Msps) compared to 66Msps). Furthermore, energy can be reduced by up to 75%
compared with commercial TCAMs in 0.18¹m CMOS technology. |
| 0905 |
Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN |
Muhammad Aamir Cheema
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: macheema@cse.unsw.edu.au
Xuemin Lin
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: lxue@cse.unsw.edu.au
Ying Zhang
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: yingz@cse.unsw.edu.au
Wei Wang
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: weiw@cse.unsw.edu.au |
In the past few years, continuous monitoring of spatial queries has received significant
attention from the database research community. In this paper, we study the problem of
continuous monitoring of reverse k nearest neighbor queries. Existing continuous reverse
nearest neighbor monitoring techniques are sensitive towards objects and queries movement.
For example, the results of a query are to be recomputed whenever the query changes its
location. We present a framework for continuous reverse k nearest neighbor queries by
assigning each object and query with a rectangular safe region such that the expensive
re-computation is not required as long as the query and objects remain in their respective
safe regions. This significantly improves the computation cost. As a by-product, our
framework also reduces the communication cost in client-server architectures because an
object does not report its location to the server unless it leaves its safe region or the
server sends a location update request. We also conduct a rigid cost analysis to guide an
effective selection of such rectangular safe regions. The extensive experiments demonstrate
that our techniques outperform the existing techniques by an order of magnitude in terms of
computation cost and communication cost. |
| 0904 |
Using Agile Practices in Global Software Development: A Systematic Review |
Emam Hossain
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: meh@cse.unsw.edu.au
Muhammad Ali Babar
Lero, University of Limerick
International Science Centre, Limerick
Ireland
E-mail: malibaba@lero.ie
Hye-young Paik
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: hpaik@cse.unsw.edu.au |
There is a growing interest in applying agile approaches in Global Software Development (GSD) projects.
Recently, some studies have reported the use of Scrum practices in distributed development projects.
However,little is known about how these practices are carried out in reality and what the outcomes are.
We have conducted a systematic literature review to identify, synthesize and present the findings from
the primary studies that report using Scrum practices in GSD projects. Our search strategy identified
583 papers, of which 20 were identified as primary papers relevant to our research. We extracted data
from these papers to identify various challenges of using Scrum in GSD. Current strategies to deal with
the identified challenges have also been extracted. This paperpresents the review’s findings that are
expected to help researchers and practitioners to understand the current state of use of Scrum practices
in GSD. |
| 0903 |
Modeling and Verification of NoC Communication Interfaces |
Vinitha Palaniveloo
School of Computer Science and Engineering
The University of New South Wales
NSW 2052, Australia
E-mail: vinithaap@cse.unsw.edu.au
Arcot Sowmya
School of Computer Science and Engineering
The University of New South Wales
NSW 2052, Australia
E-mail: sowmya@cse.unsw.edu.au
Sridevan Parameswaran
School of Computer Science and Engineering
The University of New South Wales
NSW 2052, Australia
E-mail: sridevan@cse.unsw.edu.au |
The concept of Network on Chip (NoC) addresses the communication requirements on chip and decouples communication from computation. One of the challenges faced by designers of NoC integrated circuits is verifying the correctness of communication scheme for an NoC Architecture. The NoC are on-chip communication networks that borrows the networking concept from computer networks to interconnect complex Intellectual Property (IP) on chip. Therefore, the applications on IP cores communicate with peer applications thorough communication architecture that consists of layered communication protocol, routers and switches. The absence of an integrated architectural model poses the challenge of performing end-to-end verification of communication scheme. The formal models of NoC proposed so far in the literature focus on modeling parts of communication architecture such as the specific layers of communication protocol or routers or network topology but not as a integrated architectural model. This is attributed to the absence of expressive modelling language to model all the modules of the NoC communication architecture. The NoC communication architecture is heterogeneous as it consists of synchronous and asynchronous IP cores communicating through heterogenous communication pipelines. In this project we propose a heterogenous modeling language for modelling and verification of NoC communcation architecture. The proposed modeling language is based on formal methods as they provide precise semanitics, mathematics based tools and techniques for specification and verification. |
| 0902 |
An Aspect-oriented Approach for Service Adaptation |
Woralak Kongdenfha
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: woralakk@cse.unsw.edu.au
Hamid Motahari
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: hamidm@cse.unsw.edu.au
Boualem Benatallah
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: boualem@cse.unsw.edu.au
Fabio Casati
Department of Information and Communication
University of Trento, Italy
E-mail: casati@dit.unitn.it
Regis Saint-Paul
CREATE-NET International Research Center
Trento, Italy
E-mail: regis.saint-paul@create-net.org |
Standardization in Web services simplifies integration. However, it does not remove the need for adapters due to possible heterogeneity among service interfaces and protocols. In this paper, we characterize the problem of Web services adaptation focusing on business interfaces and protocols adapters. Our study shows that many of differences between business interfaces and protocols are recurring. We introduce mismatch patterns to capture these recurring differences and to provide solutions to resolve them. We leverage mismatch patterns for service adaptation with two approaches: by developing standalone adapters and via service modification. We then dig into the notion of adaptation aspects, that, following aspect-oriented programming paradigm and service
modification approach, allow for rapid development of adapters. We present a study showing that it is a preferable approach in many cases. The proposed approach is implemented in a proof-of-concept prototype tool. We explain how it simplifies adapter development through a case study. |
| 0824 |
Hop Count Analysis for Greedy Geographic Routing |
Quanjun Chen, Salil S. Kanhere, Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: {quanc, salilk, mahbub}@cse.unsw.edu.au |
Hop count is a fundamental metric in multi-hop wireless ad-hoc network. It has a determinative effect on the performances of wireless network, such as throughput, end-to-end delay and energy consumption. Identifying hop count metric, including the distribution function and the mean value, is therefore vital for analyzing wireless network performance. This paper proposes a theoretical model to accurately analyze the hop count distribution and its mean value. Given a communication pair, its hop count metric is dependent on the routing protocol selected and the network topology determined by the physical radio model. At routing layer, our model focuses on the widely used greedy routing. At physical layer, the model investigate the ideal radio model, and a more realistic radio model, e.g. log-normal shadowing model. We conduct a rich set of simulation to validate our analytical model. The comparison results show that the simulation results closely match with the analysis results. The analytical model is further validated through a trace driven simulation of a practical vehicular ad-hoc network that exhibits realistic topologies of public transport buses in a metropolitan city. |
| 0823 |
A Formal Analysis of Phylogenetic Definitions in the PhyloCode |
Rex Kwok
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: rkwok@cse.unsw.edu.au |
Three main codes currently govern biological nomenclature:
(i) The International Code of Botanical Nomenclature (ICBN), (ii) The
International Code of Zoological Nomenclature (ICZN), and (iii) The
International Code of Nomenclature of Bacteria (ICNB). Recently, the
PhyloCode -- a code based on phylogenetic nomenclature,
has been presented as an alternative. To facilitate a comparison
between the various codes, this paper presents a formal study into
the properties of phylogenetic nomenclature -- as presented in the
PhyloCode. While much of the PhyloCode necessarily deals with the
procedures for publishing and registering names, an important
component deals with phylogenetic definitions. It is this component
that will be studied in detail here. The various types of
phylogenetic definition will be formalised in a mathematical setting.
Results will be presented
showing that under phylogenetic trees that much of the
intuition surrounding phylogenetic definitions match
up with the formalisation. However, ambiguity in the meaning of such
definitions arises under the more
general case when a phylogenetic hypothesis is allowed to be a rooted
directed acyclic graph -- a situation expressly allowed by the
PhyloCode.
Solutions to such problems will be presented.
The issue of semantic stability -- an often
stated desirable property of a nomenclatural system -- will also be
examined. Conditions will be presented showing how stability can be
improved for phylogenetic definitions.
Two new types phylogenetic definition, the minimality--based
definition and the maximality--based definition, will be presented as
generalisations of the PhyloCode definitions. How the PhyloCode
definitions relate to each other will be shown from this new
perspective. |
| 0821 |
Logic Programming Revisited from a Classical Standpoint |
Eric A. Martin
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: emartin@cse.unsw.edu.au |
Logic programming has developed as a rich field, built over a logical substratum whose main
constituent is a nonclassical form of negation, sometimes coexisting with classical negation.
The field has seen the advent of a number of alternative semantics, with Kripke-Kleene semantics,
the well founded semantics, the stable model semantics, and answer-set programming standing out as
the most successful of all. We show that using classical negation only, all aforementioned
semantics are particular cases of a unique semantics applied to a general notion of logic program
possibly transformed following a simple procedure. The notions and results presented in this paper
give a classical perspective on the field of logic programming and broaden its scope, as that
simple procedure suggests a number of possible transformations of a logic program, that can be
classified into families, some members of some of those families matching a particular paradigm
in the field. The paper demonstrates that logic programming can be developed in such a way that
negation does not present itself as an intrinsically complex operator, hard to interpret properly
and that needs a complicated formal apparatus to be fully apprehended, but still in a way that
accommodates the semantics that have put nonclassical negation at the center of their
investigations. |
| 0820 |
Distributed Optimization For Location Refinement in Ad-hoc Sensor Networks |
Sarfraz Nawaz
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: mnawaz@cse.unsw.edu.au
Chun Tung Chou
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: ctchou@cse.unsw.edu.au
Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sanjay@cse.unsw.edu.au |
A number of range based sensor network localization systems form a
rough layout of the network and then starting from this rough layout
gradually refine the location coordinates of sensor nodes. We model
this coordinate refinement as an unconstrained non-linear optimization
problem and show that current heuristic based approaches that require
empirical tunning of parameters cannot guarantee convergence in ad-hoc
network deployments. We then present a completely distributed
algorithm for location refinement and show that this problem can be
solved by iteratively performing aggregate sum computations of certain
locally computed values over the entire sensor network. Our proposed
algorithm does not require any empirical tunning and thus can work
with ad-hoc network deployments. We show through simulations and real
experimentation that our algorithm exhibits faster convergence as
compared to current empirically tunned approaches with similar overhead. |
| 0818 |
GATE: A Novel Robust Object Tracking Method Using the Particle
Filtering and Level Set Method |
Cheng Luo
School of Computer Science and Engineering
University of New South Wales
National ICT Australia
NSW 2052, Australia
E-mail: luo.cheng@nicta.com.au
Xiongcai Cai
School of Computer Science and Engineering
University of New South Wales
National ICT Australia
NSW 2052, Australia
E-mail: xcai@cse.unsw.edu.au
Jian Zhang
School of Computer Science and Engineering
University of New South Wales
National ICT Australia
NSW 2052, Australia
E-mail: jian.zhang@nicta.com.au |
This technical report presents a novel algorithm for robust object
tracking based on the particle filtering method employed in recursive
Bayesian estimation and image segmentation and optimisation techniques
employed in active contour models and level set methods. The proposed
Geometric Active contour-based Tracking Estimation, namely GATE, enables
particle filters to track object of interest in complex environments using
merely a simple feature. GATE creates a spatial prior in the state space
using shape information of the tracked object. The created spatial prior
is then used to filter particles in the state space in order to reshape
and refine the observation distribution of the particle filtering. This
improves the performance of the likelihood model in the particle
filtering, so the significantly overall improvement of the particle
filtering. The promising performances of our method on real sequences are
demonstrated. |
| 0816 |
Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data |
Muhammad Aamir Cheema
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: macheema@cse.unsw.edu.au
Xuemin Lin
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: lxue@cse.unsw.edu.au
Wei Wang
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: weiw@cse.unsw.edu.au
Wenjie Zhang
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: zhangw@cse.unsw.edu.au
Jian Pei
School of Computer Science
Simon Fraser University
Burnaby, BC Canada
E-mail: jpei@cs.sfu.ca |
Uncertain data is inherent in many important applications where the exact
data values are not known. While many types of queries on uncertain data
have been studied, reverse nearest neighbor query on uncertain data is
still an open problem. In this paper, we formalize the problem of
probabilistic reverse nearest neighbor query based on the possible worlds
semantics. We propose an efficient method that processes such queries
efficiently. The key technique innovation is several novel pruning methods
that exploit various properties of the problem. Extensive experiment
demonstrates that our algorithm is highly efficient and scalable. |
| 0815 |
Context-Aware Channel Coordination for Vehicular Communications |
Zhe Wang
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: zhewang@cse.unsw.edu.au
Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: mahbub@cse.unsw.edu.au |
Vehicular communication could be the much anticipated breakthrough against the
unabated fatal and near fatal accidents that continue to threaten the public
safety on our roads. The same technology is also expected to concurrently
support a range of non-safety applications including real-time traffic
information, mobile entertainment, and access to the Internet. The standard has
specified an explicit multi-channel structure whereby safety and non-safety
transmissions will occur at different channels. Consequently, a vehicle with a
conventional single-radio transceiver will need to continuously switch between
the safety and the non-safety modes of operation. The interval spent in the
safety mode (safety interval) at each cycle is a critical parameter that
directly limits the availability of the technology for commercial use. Using
simulation, we show that the safety interval required to satisfy the reliability
of safety applications is a function of traffic density on the road. Given that
in most roads traffic density is expected to vary during the day, we propose
dynamic adjustment of the safety interval based on the traffic context. To
further motivate the concept of traffic aware vehicular communications, we
evaluate the performance of three dynamic channel coordination algorithms using
empirical traffic data collected from the roads around the city of Sydney,
Australia. A key finding is that, the time-of-day is an effective context that
can prevent a vehicular radio from keep running in the safety mode
unnecessarily, thereby enhancing the commercial opportunity of the technology.
We further demonstrate that the use of the location context can dramatically
improve the performance of the basic time-of-day algorithms. |
| 0814 |
How Much of DSRC is Available for Non-Safety Use? |
Zhe Wang
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: zhewang@cse.unsw.edu.au
Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: mahbub@cse.unsw.edu.au |
The Dedicated Short Range Communication (DSRC) technology is currently being
standardized by the IEEE to enable a range of communication-based automotive
safety applications. However, for DSRC to be cost-effective, it is important to
accommodate commercial non-safety use of the spectrum as well. The co-existence
of safety and non-safety is achieved through a periodic channel switching scheme
whereby access to DSRC alternates between these two classes of applications. In
this paper, we propose a framework that links the non-safety share of DSRC as
effected by the channel switching to the performance requirements of safety
applications. Using simulation experiments, we analyze the non-safety
opportunity in the DSRC under varied road traffic conditions. We find that
non-safety use of DSRC may have to be severely restricted during peak hours of
traffic to insure that automotive safety is not compromised. Our study also
sheds interesting insights into how simple strategies, e.g., optimizing the
message generation rate of the safety applications, can significantly increase
the commercial opportunities of DSRC. Finally, we find that adaptive schemes
that can dynamically adjust the switching parameters in response to observed
traffic conditions may help in maximizing the commercial use of DSRC. |
| 0812 |
A Measurement Study of Bandwidth Predictability in Mobile Communication
Networks |
Jun Yao, Salil S. Kanhere, Mahbub Hassan
School of Computer Science and Engineering,
University of New South Wales,
Australia
Email: {jyao, salilk, mahbub}@cse.unsw.edu.au |
While bandwidth predictability has been well studied in static
environments, it remains largely unexplored in the context of mobile
computing. To gain a deeper understanding of this important issue in
the mobile environment, we conducted an eight-month measurement
study consisting of 71 repeated trips along a 23Km route in Sydney
under typical driving conditions. To account for the network
diversity, we measure bandwidth from two independent cellular
providers implementing the popular High-Speed Downlink Packet Access
(HSDPA) technology in two different peak access rates (1.8 and 3.6
Mbps). Interestingly, we observe no significant correlation between
the bandwidth signals at different points in time within a given
trip. This observation eventually leads to the revelation that the
popular time series models, e.g. the Autoregressive and Moving
Average, typically used to predict network traffic in static
environments are not as effective in capturing the regularity in
mobile bandwidth. Although the bandwidth signal in a given trip
appears as a random white noise, we are able to detect the existence
of patterns by analyzing the distribution of the bandwidth observed
during the repeated trips. We quantify the bandwidth
predictability reflected by these patterns using tools from
information theory, entropy in particular. The entropy
analysis reveals that the bandwidth uncertainty may reduce by as
much as 46% when observations from past trips are accounted for. We
further demonstrate that the bandwidth in mobile computing appears
more predictable when location is used as a context. All these
observations are consistent across multiple independent providers
offering different data transfer rates using possibly different
networking hardware. |
| 0811 |
Interference Analysis and Channel Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks |
Anjum Naveed
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: anaveed@cse.unsw.edu.au
Salil Kanhere
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: salilk@cse.unsw.edu.au |
In a typical Wireless Mesh Network (WMN), the links that interfere with a particular link can be broadly classified into two categories depending on their geometric relationships: coordinated and non-coordinated links. In this paper, we analytically quantify the impact of both kind of interfering links on transmission losses. Our analysis shows that compared to coordinated links, the non-coordinated links result in significantly lower throughput and an unfair distribution of channel capacity amongst interfering links. We hypothesize that channel assignment in multi-radio multi-channel WMNs can be effective in significantly reducing the interference caused by the non-coordinated links. We prove that the channel assignment problem based on this hypothesis is NP-Hard. We propose a novel two-phase heuristic channel assignment protocol referred as Cluster-Based Channel Assignment Protocol (CCAP). The protocol logically partitions the network into non-overlapping clusters. In the first phase, nodes within a cluster are assigned to a common channel with orthogonal channels being used in adjacent clusters. The inter-cluster links are assigned channels with the aim of minimizing non-coordinated interference. The second phase of CCAP exploits channel diversity to sub-divide each cluster into multiple interference domains, thereby increasing the capacity of individual links. Simulation-based evaluations demonstrate that CCAP can achieve twice the aggregate network throughput as compared to existing channel assignment protocols, while ensuring a fair distribution of capacity amongst the links. |
| 0810 |
Mashups for Data Integration: An Analysis |
Giusy Di Lorenzo
Dipartimento di Informatica e Sistemistica
University Federico II
Via Claudio, 21
80125 Napoli, Italy
E-mail: giusy.dilorenzo@unina.it
Hakim Hacid
School of Computer Science Engineering
University of new south wales
Sydney, NSW 2052, Australia
E-mail: hakimh@cse.unsw.edu.au
Hye-young Paik
School of Computer Science and Engineering
University of new south wales
Sydney, NSW 2052, Australia
E-mail: hpaik@cse.unsw.edu.au
Boualem Benatallah
School of Computer Science and Engineering
University of new south wales
Sydney, NSW 2052, Australia
E-mail: boualem@cse.unsw.edu.au |
Mashup is a new application development approach that allows users aggregate multiple services,
each serving its own purpose, to create a service that serves a new purpose.
Even if the Mashup approach opens new and broader opportunities for data/service consumers,
the development process still requires the users to know, not only understand how to write code using languages,
but also how to use the different Web APIs from all services.
The objective of this study is to analyze the richnesses and weaknesses of the Mashup tools.
In particular, we identify the behaviors and characteristics of general
Mashup applications and analyze the tools with respect to the key aspects from the Mashup applications.
We believe that this kind of study is important to drive future contributions in this emerging area where a
lot of research and application fields, such as databases, user machine interaction, etc., can meet. |
| 0809 |
Mix and Test Counting in Preferential Electoral Systems |
Roland Wen, Richard Buckland
School of Computer Science and Engineering
University of New South Wales
Sydney, NSW 2052, Australia
E-mail: {rolandw,richardb}@cse.unsw.edu.au |
Although there is a substantial body of work on online voting schemes that
prevent bribery and coercion of voters, as yet there are few suitable schemes
for counting in the alternative vote and single transferable vote preferential
systems. Preferential systems are prone to bribery and coercion via signature
attacks. This is an issue for online elections in Australia, where all
parliamentary elections use these preferential systems. We present the Mix and
Test Counting scheme, a preferential counting protocol that is resistant to
signature attacks. For the alternative vote, it reveals no information apart
from the identity of the winning candidate. For the single transferable vote,
it reveals additional anonymised counting information. However the only
candidates identified are the winning candidates. |
| 0808 |
Herbrand Analysis of Some Second-order Theories with Weak Set
Existence Principles |
Chung Tong Lee
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: ctlee@cse.unsw.edu.au
Aleksandar Ignjatovic
School of Computer Science and Engineering
University of New South Wales, and
NICTA
NSW2052, Australia
Email: ignjat@cse.unsw.edu.au |
We present a proof-theoretic analysis of some second-order theories of binary
strings which were introduced in [5]. The core of these theories contains,
besides finitely many open axioms for basic operations on strings, only a
weak comprehension axiom schema. In such theories, a collection W can be
defined to play the role of natural numbers. W is given as the intersection
of all sets containing the empty string and closed under the two successor
functions S0 and S1. We characterize the classes of functions which provably
map W into itself and whose graphs are defined by formulas of an appropriate
bounded quantifier complexity. For theories with weak comprehension
schemas, this notion corresponds naturally to that of provably recursive
functions for arithmetic theories. The techniques of Herbrand analysis developed
by Sieg in [8] and [9] allow us to prove that these classes match up
with levels of the polynomial-time hierarchy. |
| 0807 |
Masked Ballot Receipt-Free Elections |
Roland Wen
School of Computer Science and Engineering
University of New South Wales
Sydney, NSW 2052, Australia
E-mail: rolandw@cse.unsw.edu.au |
Online election schemes mitigate bribery and coercion by precluding the
generation of receipts that can prove how voters voted. In order to guarantee
that each voter's public election data appears ambiguous, existing approaches
to receipt-free schemes rely on problematic assumptions when voters cast
ballots. We take a new approach by using the novel properties of the
Damgard-Jurik cryptosystem to construct Masked Ballot, a receipt-free scheme
that avoids such assumptions during the election. The Masked Ballot scheme
assumes the existence of untappable channels for a trusted registrar to send
private masking values to voters before the election, but does not require
these channels during the election. Voters cast ballots over completely public
channels without relying on untappability, anonymity or trusted devices. |
| 0806 |
Towards Agile Service-oriented Business Systems: A
Directive-oriented Pattern Analysis Approach |
Soo Ling Lim
School of Computer Science and Engineering
University of New South Wales, and
NICTA, Australian Technology Park
Sydney, Australia
Email: slim@cse.unsw.edu.au
Fuyuki Ishikawa, Eric Platon
National Institute of Informatics
Tokyo, Japan
Email: {f-ishikawa,platon}@nii.ac.jp
Karl Cox
NICTA, Australian Technology Park
Sydney, Australia
Email: Karl.Cox@nicta.com.au |
Volatile requirements should be managed such that changes can be
introduced into the system in a quick and structured way. This paper
presents Directive-oriented Pattern Analysis (DoPA), a requirements
engineering approach that handles volatile requirements by managing the
coupling between business intentions and service integration. The key
insight is to utilise services as commodities via service choreography
patterns. DoPA captures differentiating enterprise intentions as
Directives, while using patterns to handle common business needs. This
enables the notion of declarative configuration of services to achieve
business agility. |
| 0805 |
Adapting the Weighted Backtrack Estimator to Conflict Driven Search |
Shai Haim
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: shaih@cse.unsw.edu.au
Toby Walsh
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: tw@cse.unsw.edu.au |
Modern SAT solvers present several challenges
to estimate search cost including coping with nonchronological
backtracking and learning. We present a method to adapt an existing algorithm for estimating the size
of a search tree to deal with these challenges. We show the effectiveness
of this method using random and structured problems. |
| 0804 |
Analysis of Per-node Traffic Load in Multi-hop Wireless Sensor Networks |
Quan Jun Chen, Salil S. Kanhere, Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: {quanc, salilk, mahbub}@cse.unsw.edu.au |
The energy expended by sensor nodes in reception and transmission of data
packets makes up a significant quantum of their total energy consumption.
Consequently, models that can accurately predict the communication
traffic load of a sensor node are critical for designing effective and
efficient sensor network protocols. In this paper, we present an
analytical model for estimating the per-node traffic load in a multi-hop
wireless sensor network, where the nodes sense the environment
periodically and forwards the data packets to the sink using greedy
geographic routing. The analysis incorporates the idealistic circular
coverage radio model as well as a realistic model, log-normal shadowing.
Our results confirm that, irrespective of the radio models, the traffic
load generally increases as a function of the node's proximity to the
sink. In the immediate vicinity of the sink, however, the two radio
models yield quite contrasting results. The ideal radio model reveals the
existence of a volcano region near the sink, where the traffic load
drops significantly. On the contrary, with the log-normal shadowing
model, the opposite effect is observed, wherein the traffic load actually
increases at a much higher rate as one approaches the sink resulting in
the formation of a mountain peak. The results from our analysis are
validated by extensive simulations. The simulations also demonstrate that
our results are applicable in more realistic environments, which do not
conform to the simplifying assumptions made in the analysis for
mathematical tractability. |
| 0803 |
Automatic collection of fuel prices from a network of mobile cameras |
Yi Fei Dong, Salil Kanhere, Chun Tung Chou
School of Computer Science and Engineering
The University of New South Wales
Sydney, NSW 2052, Australia
Email: {ydon,salilk,ctchou}@cse.unsw.edu.au
Nirupama Bulusu
Portland State University, USA
Email: nbulusu@cs.pdx.edu |
It is an undeniable fact that people want information. Unfortunately,
even in today's highly automated society, a lot of the information we
desire is still manually collected. An example is fuel prices where
websites providing fuel price information either send their workers
out to manually collect the prices or depend on volunteers manually
relaying the information. This paper proposes a novel application of
wireless sensor networks to automatically collect fuel prices from
camera images of road-side price board (billboard) of service (or gas)
stations. Our system exploits the ubiquity of mobile phones that have
cameras as well as users contributing and sharing data. In our proposed
system, cameras of contributing users will be automatically triggered
when they get close to a service station. These images will then be
processed by computer vision algorithms to extract the fuel prices.
In this paper, we will describe the system architecture and present
results from our computer vision algorithms. Based on 52 images,
our system achieves a hit rate of 92.3% for correctly detecting the
fuel price board from the image background and reads the prices correctly
in 87.7% of them. To the best of our knowledge, this is the first
instance of a sensor network being used for collecting consumer
pricing information |
| 0802 |
ERTP: Energy-efficient and Reliable Transport Protocol for Data Streaming in Wireless Sensor Networks |
Tuan Le
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: dtle@cse.unsw.edu.au
Wen Hu
CSIRO ICT Centre
Brisbane, Australia
E-mail: wen.hu@csiro.au
Peter Corke
CSIRO ICT Centre
Brisbane, Australia
E-mail: peter.corke@csiro.au
Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sanjay@cse.unsw.edu.au |
Emerging data streaming applications in Wireless Sensor Networks require re-
liable and energy-efficient transport protocols. Our recent Wireless Sensor Network deployment
in the Burdekin delta, Australia for water monitoring is one such example. Our application
involved streaming sensed data such as pressure readings, water flow rate, and salinity readings periodi-
cally from many scattered sensors to the sink node which in turn relayed them
via an IP network to a remote site for archiving, processing and presentation.
While latency is not a primary concern in this class of application (the sample
rate is usually in terms of minutes or hours), energy-efficiency is. Long-term
operation and reliable delivery of the sensed data to the sink are also desirable.
In this paper, we discuss ERTP, an Energy-efficient and Reliable Transport
Protocol for Wireless Sensor Networks. ERTP is designed for data streaming
applications, in which sensor readings are transmitted from one or more sensor
sources to a base station (or sink). ERTP uses a statistical reliability metric
which ensures the number of data packets delivered to the sink exceeds the
defined threshold. Using a statistical reliability metric when designing a reliable
transport protocol guarantees the delivery of adequate information to the users,
and reduces the number of transmissions when compared to absolute reliability.
To reduce energy-consumption, ERTP uses hop-by-hop Implicit Acknowl-
edgment with dynamically updated retransmission timeout for loss recovery. In
multihop wireless networks, the transmitter can overhear a forwarding trans-
mission and interpret it as an Implicit Acknowledgment. However, Implicit
Acknowledgment timeout depends on the time taken a packet to be forwarded
by the downstream node. Thus, a dynamic retransmission timeout estimation
is crucial for the class of Hop-by-Hop Implicit Acknowledgment transport pro-
tocol.
By combining statistical reliability and hop-by-hop Implicit ACK loss re-
covery, ERTP can provide the reliability to application users with the mini-
mal energy-expense. Our extensive discrete event simulations and experimental
evaluations show that ERTP is significantly more energy-efficient than current
approaches and can reduce energy consumption by more than 50% when com-
pared to current approaches. Consequently, sensors are more energy-efficient
and the lifespan of the unattended WSN is increase |
| 0801 |
Analytical Evaluation of the 802.11 Wireless Broadcast under Saturated Conditions |
Zhe Wang and Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: {zhewang, mahbub}@cse.unsw.edu.au |
The popular IEEE 802.11 wireless networking standard has been traditionally used for unicast communications. There is, however, a recent trend in harnessing the broadcast capability of the standard in a range of monitoring and safety related applications, e.g., transportation safety and vehicular traffic management. As this trend continues, models that accurately predict the performance of the 802.11 broadcast will be increasingly useful. Although unicast modelling received considerable attention, analytical evaluation of the broadcast protocol remained relatively unexplored. Using a simple one-dimensional discrete time Markov chain, we analyse the reliability and throughput performance of the IEEE 802.11 broadcast communications for saturated traffic conditions. The model is validated by means of an independent commercial simulator. Using the proposed model, we provide an extensive performance analysis of the 802.11 broadcast communications. The analysis allows us to study the tradeoff between the communication reliability and the system throughput of a local area wireless broadcast network. The throughput performance of broadcast is compared with that of the unicast under different network sizes and different combinations of 802.11 protocol parameters. |
| 0723 |
Tool support for verifying trace inclusion with Uppaal |
Timothy Bourke
NICTA, Kensington Laboratory, and
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: tbourke@cse.unsw.edu.au
Arcot Sowmya
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sowmya@cse.unsw.edu.au |
Trace inclusion against a deterministic Timed Automata can be verified with
the Uppaal model checking tool by constructing a test automaton that snares
illegal synchronisation possibilities. Constructing the automaton manually
is tedious and error prone. This paper presents a tool that does it
automatically for a subset of Uppaal models.
Certain features of Uppaal, namely selection bindings and channel arrays,
complicate the construction. We first formalise these features, and then
show how to incorporate them directly in the testing construction. To do so
we limit the forms of subscript that can be used to specify
synchronisations; striving for a balance between practicability and program
complexity. Unfortunately, some combinations of selection bindings and
universal quantifiers cannot be effectively manipulated. The tool does not
yet validate the determinism requirements, nor handle committed states or
broadcast channels. |
| 0722 |
Time-Aware Content Summarization of Data Streams |
Quang-Khai Pham, R´egis Saint-Paul, Boualem Benatallah
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
Guillaume Raschia, Noureddine Mouaddib
Atlas Group
LINA at University of Nantes
Nantes, France |
Major media companies such as The Financial Times, the Wall Street
Journal or Reuters generate huge amounts of textual news data on a daily
basis. Mining frequent patterns in this mass of information is critical
for knowledge workers such as financial analysts, stock traders or
economists. Using existing frequent pattern mining (FPM) algorithms for
the analysis of news data is difficult because of the size and lack of
structuring of the free text news content. In this article, we propose a
Time-Aware Content Summarization algorithm to support FPM in financial
news data. The summary allows a concise representation of large volume
of data by taking into account the expert's peculiar interest. The
summary also preserves the news arrival time information which is
essential for FPM algorithms. We experimented the proposed approach on
Reuters news data and integrated it into the Streaming TEmporAl Data
(STEAD) analysis framework for interactive discovery of frequent
pattern. |
| 0721 |
Process Spaceship: Discovering Process Views in Process Spaces |
Hamid Reza Motahari-Nezhad, R´egis Saint-Paul, Boualem Benatallah
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
Fabio Casati, Periklis Andritsos
University of Trento
Trento, Italy |
Process and service execution analysis is a key endeavour for enterprises.
Such analysis requires observing and correlating messages related to process and service executions,
meaning that identifying if messages belong to the same process instance or service execution.
A first challenge is that message correlation is subjective, i.e., depends on the purpose
of the analysis and on the perspective of the analyst. Another challenge lies in the
huge space of possible correlations between messages, which can be built based on
different combinations of message attributes.
In this paper, we consider process and service execution data as a process space,
and different ways of performing correlations as process views that are views
over the process space. We propose methods, by adopting a level-wise approach,
and heuristics to identify the set of interesting process views and present a
visual, interactive environment that allows users to efficiently navigate
through the views identified over a process space.
The experiments show the viability and efficiently of
the approach on both synthetic and real-world service logs. |
| 0719 |
Experience and Trust: A Sytems-Theoretic Approach |
Rex Kwok and Norman Foo
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {rkwok|norman}@cse.unsw.edu.au
Abhaya Nayak
Department of Computing
Division of Information and Communication Sciences
Macquarie University, NSW 2109, Australia
Email: abhaya@ics.mq.edu.au |
The core of scientific theories are laws. These laws often
make use of theoretical terms, linguistic entities which do not
directly refer to observables. There is therefore no direct way
of determining which theoretical assertions are true. This suggests
that multiple theories may exist which are incompatible with one
another but compatible with all possible observations. Since such
theories make the same empirical claims, empirical tests cannot be
used to differentiate or rank such theories. One property that has
been suggested for evaluating rival theories is coherence.
This was investigated qualitatively until we introduced a coherence
measure based on the average use of formulas in support sets for
observations. Our idea was to identify highly coherent theories
with those whose formulas that are tightly coupled to account for
observations, while low coherence theories contain many disjointed
and isolated statements. The present paper generalizes it to
accommodate fundamental intuitions from the philosophy of science
and better mirrors scientific practice. Moreover, this new approach
is neutral with respect to the philosophy and practice of science,
and is able to explain notions like modularization using coherence. |
| 0718 |
Protocol Compatibility and Automatic Converter Synthesis |
Karin Avnit
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: kavnit@cse.unsw.edu.au
Vijay D'Silva
Department of Computer Science,
ETH Zurich
CH-8092 Zurich, Switzerland
E-mail: vdsilva@inf.ethz.ch
Arcot Sowmya
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sowmya@cse.unsw.edu.au
S. Ramesh
GM India Science Lab
Bangalore India
E-mail: rameshari1958@gmail.com
Sri Parameswaran
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sridevan@cse.unsw.edu.au |
Hardware module reuse is a standard solution to deal with the increasing complexity
of chip architectures and growing pressure to reduce time to market. In the absence
of a single module interface standard, pre-designed modules for “plug and play”
usually require a converter between incompatible interface protocols. Current
approaches to automatic synthesis of protocol converters mostly lack formal
foundations and either employ abstractions far removed from implementation or
grossly simplify the structure of the protocols considered. In this work, we
present a state-machine based formalism for modeling bus based communication
protocols, a notion of protocol compatibility and of correct conversion between
incompatible protocols. Using this formalism, we derive algorithms for checking
protocol compatibility and for automatic converter synthesis. We report our
experience with automatic converter synthesis between different configurations of
widely used commercial bus protocols, such as AMBA AHB, ASB APB, and the open core
protocol (OCP). The presented work is unique in its combination of a complete
formal approach and the use of low abstraction level that enables precise modeling
of protocol characteristics and simple translation to HDL. |
| 0717 |
Experience and Trust: A Sytems-Theoretic Approach |
Norman Foo
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: norman@cse.unsw.edu.au
Jochen Renz
Research School of Information Science and Engineering
Australian National University
Canberra ACT 2600, Australia
E-mail: jochen.renz@anu.edu.au |
An influential model of agent trust and experience is that of Jonker and
Treur. In that model an agent uses its experience of the interactions of
another agent to assess its trustworthiness. We show here that a key
property of that model is subsumed by a result of classical mathematical
systems theory. Using the latter theory we also clarify the issue of
when two experience sequences may be regarded as equivalent. An
intuitive feature of the Jonker and Treur model is that experience
sequence orderings are respected by functions that map such sequences to
trust orderings. We raise a question about another intuitive property --
that of continuity of these functions, viz. that they map experience
sequences that resemble each other to trust values that also resemble
each other. Using fundamental results in the relationship between
partial orders and topologies we also show that these two intutive
properties are essentially equivalent. |
| 0716 |
Localized Minimum-Latency Broadcasting in Multi-Radio Multi-Channel Multi-Rate Wireless Mesh Networks |
J. Qadir, C.T. Chou, J.G. Lim
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {junaidq,ctchou,jool}@cse.unsw.edu.au
Archan Misra
Research Staff Member,
Next-Generation Web Infrastructure Dept.
IBM T J Watson Research Center
19 Skyline Drive,
Hawthorne, NY 10532, USA
Email: archan@us.ibm.com |
We address the problem of minimizing the worst-case broadcast delay in ``multi-radio multi-channel multi-rate wireless mesh networks'' (MR2-MC WMN) in a distributed and localized fashion. Efficient broadcasting in such networks is especially challenging due to the desirability of exploiting the ``wireless broadcast advantage'' (WBA), the interface-diversity, the channel-diversity and the rate-diversity offered by these networks. We propose a framework that calculates a set of forwarding nodes and transmission rate at these forwarding nodes irrespective of the broadcast source. Thereafter, a forwarding tree is constructed taking into consideration the source of broadcast. Our broadcasting algorithms are distributed and utilize locally available information. To the best of our knowledge, this works constitutes the first contribution in the area of distributed broadcast in multi-radio multi-rate wireless mesh networks. We present a detailed performance evaluation of our distributed and localized algorithm and demonstrate that our algorithm can greatly improve
broadcast performance by exploiting the rate, interface and channel diversity of MR2-MC WMNs and match the performance of centralized algorithms proposed in literature while utilizing only limited two-hop neighborhood information. |
| 0715 |
Solving the expression problem in Haskell with true separate
compilation |
Sean Seefried
Formal Methods
NICTA
Email: sean.seefried@nicta.com.au
Manuel M. T. Chakravarty
Programming Languages and Systems
School of Computer Science & Engineering
University of New South Wales
Email: chak@cse.unsw.edu.au |
We present a novel solution to the expression problem which offers
true separate compilation and can be used in existing Haskell
compilers that support multi-parameter type classes and recursive
dictionaries. The solution is best viewed as both a programming
idiom, allowing a programmer to implement open data types and open
functions, and the target encoding of a translation from Haskell
augmented with syntactic sugar. |
| 0714 |
Resource-aware Broadcast and Multicast in Multi-rate Wireless
Mesh Networks |
Bao Hua Liu
Thales Australia - Joint Systems, Garden Island, NSW 2011, Australia
Chun Tung Chou
School of Computer Science and Engineering,
University of New South Wales, Australia
ctchou@cse.unsw.edu.au
Archan Misra
IBM T J Watson Research Center,
Hawthorne, New York, USA
archan@us.ibm.com
Sanjay Jha
School of Computer Science and Engineering,
University of New South Wales, Australia |
This paper studies some of the fundamental challenges and opportunities
associated with the network-layer broadcast and multicast in a multihop
multirate wireless mesh network (WMN). In particular, we focus on
exploiting the ability of nodes to perform link-layer broadcasts at
different rates (with correspondingly different coverage areas). We
first show how, in the broadcast wireless medium, the available capacity
at a mesh node for a multicast transmission is not just a function of
the aggregate pre-existing traffic load of other interfering nodes, but
intricately coupled to the actual (sender, receiver) set and the
link-layer rate of each individual transmission. We then present and
study six alternative heuristic strategies for computing a broadcast
tree that not only factors in a flow's traffic rate but also exploits
the wireless broadcast advantage (WBA). Finally, we demonstrate how our
insights can be extended to multicast routing in a WMN, and present
results that show how a tree-formation algorithm that combines
contention awareness with transmission rate diversity can significantly
increase the total amount of admissible multicast traffic load in a WMN. |
| 0713 |
A Stronger Notion of Equivalence for Logic Programs |
Ka-Shu Wong
School of Computer Science and Engineering
and National ICT Australia
University of New South Wales
NSW 2052, Australia
E-mail: kswong@cse.unsw.edu.au |
Several different notions of equivalence have been proposed for logic
programs with answer set semantics, most notably strong equivalence.
However, strong equivalence is not preserved by certain logic program
operators such as the strong and weak forgetting operators of Zhang
and Foo, in the sense that two programs which are strongly equivalent
may no longer be strongly equivalent after the same operator is applied
to both. We propose the stronger notion of T-equivalence which is
designed to be preserved by logic program operators such as strong and
weak forgetting. We give a syntactic definition of T-equivalence and
provide a model-theoretic characterisation of T-equivalence using what
we call T-models. We show that strong and weak forgetting does preserve
T-equivalence and using this, arrive at a model-theoretic definition of
the strong and weak forgetting operators using T-models. |
| 0712 |
Protocol Compatibility and Automatic Converter Synthesis |
Karin Avnit
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia.
E-mail: kavnit@cse.unsw.edu.au
Vijay D'Silva
Department of Computer Science,
ETH Zurich
CH-8092 Zurich, Switzerland.
E-mail: vdsilva@inf.ethz.ch
Arcot Sowmya
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia.
E-mail: sowmya@cse.unsw.edu.au
S. Ramesh
GM India Science Lab
Bangalore, India.
E-mail: rameshari1958@gmail.com
Sri Parameswaran
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sridevan@cse.unsw.edu.au |
Hardware module reuse is common practice to deal with the increasing complexity
of chip architectures and growing pressure to reduce time to market. In the
absence of module interface standards, use of pre-designed modules in a "plug and
play" fashion usually requires a converter between incompatible interface protocols.
Though several approaches to such mediation have been proposed in the past,
automation of protocol converter synthesis is yet to be realized.
In this work, we present a state-machine based formalism for modeling bus based
communication protocols, a notion of protocol compatibility and of protocol conversion.
Using this formalism, we devise algorithms for checking protocol compatibility and
for automatic converter synthesis. We report our experience with automatic converter
synthesis for commercial bus protocols.
The presented work is unique in its low abstraction level that enables precise
modeling of protocol characteristics and simple translation to HDL. |
| 0711 |
Topology Control and Channel Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks |
Anjum Naveed
School of Computer Science and Engineering
The University of New South Wales,
NSW 2052, Australia
E-mail: anaveed@cse.unsw.edu.au
Salil S. Kanhere
School of Computer Science and Engineering
The University of New South Wales,
NSW 2052, Australia
E-mail: salilk@cse.unsw.edu.au
Sanjay K. Jha
School of Computer Science and Engineering
The University of New South Wales,
NSW 2052, Australia
E-mail: sjha@cse.unsw.edu.au |
The aggregate capacity of wireless mesh networks can be
improved significantly by equipping each node with multiple
interfaces and by using multiple channels in order to reduce the
effect of interference. Efficient channel assignment is required to
ensure the optimal use of the limited channels in the radio
spectrum. In this paper, a Cluster-based Multipath Topology control
and Channel assignment scheme (CoMTaC), is proposed, which
explicitly creates a separation between the channel assignment and
topology control functions, thus minimizing flow disruptions. A
cluster-based approach is employed to ensure basic network
connectivity. Intrinsic support for broadcasting with minimal
overheads is also provided. CoMTaC also takes advantage of the
inherent multiple paths that exist in a typical WMN by constructing
a spanner of the network graph and using the additional node
interfaces. The second phase of CoMTaC proposes a dynamic
distributed channel assignment algorithm, which employs a novel
interference estimation mechanism based on the average link-layer
queue length within the interference domain. Partially overlapping
channels are also included in the channel assignment process to
enhance the network capacity. Extensive simulation based experiments
have been conducted to test various parameters and the effectiveness
of the proposed scheme. The experimental results show that the
proposed scheme outperforms existing dynamic channel assignment
schemes by a minimum of a factor of 2. |
| 0710 |
Generative Code Specialisation for High-Performance Monte-Carlo
Simulations |
Don Stewart(1)
Hugh Chaffey-Millar(2)
Gabriele Keller(1)
Manuel M. T. Chakravarty(1)
Christopher Barner-Kowollik(2)
(1) Programming Languages and Systems
School of Computer Science & Engineering
University of New South Wales
(2) Centre for Advanced Macromolecular Design
School of Chemical Sciences and Engineering
University of New South Wales |
We address the tension between software generality and performance
in the domain of scientific and financial simulations based on
Monte-Carlo methods. To this end, we present a novel software
architecture, centred around the concept of a specialising simulator
generator, that combines and extends methods from generative
programming, partial evaluation, runtime code generation, and
dynamic code loading. The core tenet is that, given a fixed
simulator configuration, a generator in a functional language can
produce low-level code that is more highly optimised than a manually
implemented generic simulator. We also introduce a skeleton, or
template, capturing a wide range of Monte-Carlo methods and use it
to explain how to design specialising simulator generators and how
to generate parallelised simulators for multi-core and
distributed-memory multiprocessors.
We evaluated the practical benefits and limitations of our approach
by applying it to a highly relevant problem in computational
chemistry. More precisely, we used a Markov-chain Monte-Carlo
method for the study of advanced forms of polymerisation kinetics.
The resulting implementation executes faster than all competing
software products, while at the same time also being more general.
The generative architecture allows us to cover a wider range of
chemical reactions and to target a wider range of high-performance
architectures (such as PC clusters and SMP multiprocessors).
We show that it is possible to outperform low-level languages with
functional programming in domains with very stringent performance
requirements if the domain also demands generality. |
| 0709 |
Message Correlation for Conversation Reconstruction in Service Interaction Logs |
Hamid Reza Motahari-Nezhad, R´egis Saint-Paul, Boualem Benatallah
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
Fabio Casati, Periklis Andritsos
University of Trento
Trento, Italy |
The problem of understanding the behavior of business processes and of services is rapidly becoming a priority in medium and large companies. To this end, recently, analysis tools as well as variations of data mining techniques have been applied to process and service execution logs to perform OLAP-style analysis and to discover behavioral (process and protocol) models out of execution data. All these approaches are based on one key assumption: events describing executions and stored in process and service logs include identifiers that allow associating each event to the process or service execution they belong to (e.g., can correlate all events related to the processing of a certain purchase order or to the hiring of a given employee).
In reality, however, such information rarely exists.
In this paper, we present a framework for discovering correlations among messages in service logs. We characterize the problem of message correlation and propose novel algorithms and techniques based on well-funded principles and heuristics on the characteristics of conversations and of message attributes that can act as identifier for such conversations.
As we will show, there is no right or wrong way to correlate messages, and such correlation is necessarily subjective. To account for this subjectiveness, we propose an approach where algorithms suggest candidate correlators, provide measures that help users understand the implications of choosing a given correlators, and organize candidate correlators in such a way to facilitate visual exploration.
The approach has been implemented and experimental results show its viability and scalability on large synthetic and real-world datasets.
We believe that message correlation is a very important and challenging area of research that will witness many contributions in the near future due to the pressing industry needs for process and service execution analysis. |
| 0708 |
SPARK: Top-k Keyword Query in Relational Databases |
Yi Luo (1), Xuemin Lin (1), Wei Wang (1), and Xiaofang Zhou (2)
1: School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {luoyi, lxue, weiw}@cse.unsw.edu.au
2: School of Information Technology and Electrical Engineering
University of Queensland
Australia
E-mail: zxf@itee.uq.edu.au |
With the increasing amount of text data stored in relational
databases, there is a demand for RDBMS to support keyword queries
over text data. As a search result is often assembled from multiple
relational tables, traditional IR-style ranking and query evaluation
methods cannot be applied directly.
In this paper, we study the effectiveness and the efficiency issues
of answering top-k keyword query in relational database systems. We
propose a new ranking formula by adapting existing IR techniques
based on a natural notion of virtual document. Compared with
previous approaches, our new ranking method is simple yet effective,
and agrees with human perceptions. We also study efficient query
processing methods for the new ranking method, and propose
algorithms that have minimal accesses to the database. We have
conducted extensive experiments on large-scale real databases using
two popular RDBMSs. The experimental results demonstrate significant
improvement to the alternative approaches in terms of retrieval
effectiveness and efficiency. |
| 0707 |
Adapting Web Service Interfaces and Protocols Using Adapter Simulation |
Hamid R. Motahari Nezhad, Boualem Benatallah
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
Axel Matren, Francisco Curbera
IBM TJ Watson Research Center
New York, USA
Fabio Casati
University of Trento
Trento, Italy |
In today’sWeb, many functionality-wise similarWeb services are offered through
heterogeneous interfaces (operation definitions) and business protocols (ordering
constraints defined on legal operation invocation sequences). The typical approach
to enable interoperation in such a heterogeneous setting is through developing
adapters. There have been approaches for classifying possible mismatches between
service interfaces and business protocols to facilitate adapter development.
However, the hard job is that of identifying, given two service specifications, the
actual mismatches between their interfaces and business protocols.
In this paper we present novel techniques and a tool that provides semi-automated
support for identifying and resolution of mismatches between service interfaces
and protocols, and for generating adapter specification. We make the following
main contributions: (i) we identify mismatches between service interfaces, which
leads to finding mismatches of type of signature, merge/split, and extra/missing
messages; (ii) we identify all ordering mismatches between service protocols and
generate a tree, called mismatch tree, for mismatches that require developers’ input
for their resolution. In addition, we provide semi-automated support in analyzing
the mismatch tree to help in resolving such mismatches. We have implemented
the approach in a tool inside IBM WID (WebSphere Integration Developer). Our
experiments with some real-world case studies show the viability of the proposed
approach. The methods and tool are significant in that they considerably simplify
the problem of adapting services so that interoperation is possible. |
| 0706 |
The Operational Semantics of Dual Logic Programming |
Eric A. Martin
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia |
Many developments in the field of Logic programming reveal poor choices
of basic concepts, and misleading views on negation. We show that Logic
programming can enjoy a general, simple and clean foundation, provided
that the basic concepts be revisited, and that any nonclassical form of
negation, in particular, negation as finite failure, be disregarded. We
propose a framework that starts with a ruled-based notion of dual logic
program, allowing negation to appear in the heads as well as in the
bodies of the rules. Dual logic programs can be treated as very general
logic programs, but it is conceptually more beneficial to view them as
redefined logic programs. Classical semantics, such as the Kripke-Kleene
semantics, the well-founded semantics, and the stable model semantics,
are redefined as natural program transformations of the same kind,
resulting into dual logic programs whose behaviors can be described in
terms of the same notion of logical consequence in a classical semantics.
A kind of inference `in the style of Logic programming' from arbitrary
theories is presented, together with a natural method to transform
arbitrary theories into dual logic programs. |
| 0705 |
WS-Policy4MASC – A WS-Policy Extension Used in the Manageable and Adaptable Service Compositions (MASC) Middleware |
Vladimir Tosic, Abdelkarim Erradi, Piyush Maheshwari
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia |
WS-Policy4MASC is a new XML language that we have developed for policy specification in the Manageable and Adaptable Service Compositions (MASC) middleware. It can be also used for other Web service middleware. It extends the Web Services Policy Framework (WS-Policy) by defining new types of policy assertions. Goal policy assertions specify requirements and guarantees (e.g., maximal response time) to be met in desired normal operation. They guide monitoring activities in MASC. Action policy assertions specify actions to be taken if certain conditions are met or not met (e.g., some guarantees were not satisfied). They guide adaptation and other control actions. Utility policy assertions specify monetary values assigned to particular situations (e.g., execution of some action). They can be used by MASC for billing and for selection between alternative action policy assertions. Meta-policy assertions can be used to specify which action policy assertions are alternative and which conflict resolution strategy (e.g., profit maximization) should be used. In addition to these 4 new types of policy assertions, WS-Policy4MASC enables specification of additional information that is necessary for run-time policy-driven management. This includes information about conditions when policy assertions are evaluated/ executed, parties performing this evaluation /execution, a party responsible for meeting a goal policy assertion, ontological meaning, monitored data items, states, state transitions, schedules, events, and various expressions. We have evaluated feasibility of the WS-Policy4MASC solutions by implementing a policy repository and other modules in MASC. Further, we have examined their usefulness on a set of realistic stock trading scenarios. |
| 0704 |
Localized Minimum-Latency Broadcasting in Multi-rate Wireless Mesh Networks |
Junaid Qadir (^1), Chun Tung Chou (^1), Archan Misra (^2) and Joo Ghee Lim
(^1)
1: School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: [junaidq, ctchou, jool]@cse.unsw.edu.au
2: IBM T J Watson Research Center
19 Skyline Drive,
Hawthorne, NY 10532, USA
E-mail: archan@us.ibm.com |
We address the problem of minimizing the worst-case broadcast delay in multi-rate wireless mesh networks (WMN) in a distributed and localized fashion. Efficient broadcasting in such networks is especially challenging due to the multi-rate transmission capability and the interference between wireless transmissions of WMN nodes. We propose connecting dominating set (CDS) based broadcast routing approach which calculates the set of forwarding nodes and the transmission rate at each forwarding node independent of the broadcast source. Thereafter, a forwarding tree is constructed taking into consideration the source of the broadcast. In this paper, we propose three distributed and localized rate-aware broadcast algorithms. We compare the performance of our distributed and localized algorithms with previously proposed centralized algorithms and observe that the performance gap is not large. We show that our algorithms greatly improve performance of rate-unaware broadcasting algorithms by incorporating rate-awareness into the broadcast tree construction algorithm process. |
| 0703 |
Sensing Data Market: Architecture, Applications and Challenges |
Chun Tung Chou
School of Computer Science and Engineering,
University of New South Wales, Australia
ctchou@cse.unsw.edu.au
Nirupama Bulusu
Department of Computer Science,
Portland State University,
USA
nbulusu@cs.pdx.edu
Salil Kanhere
School of Computer Science and Engineering,
University of New South Wales, Australia
salilk@cse.unsw.edu.au |
With the rapid development of the Internet and various form of wireless
communication technologies, information-on-demand has become a reality,
e.g. people today routinely receive news items, stock prices etc. via
their mobile phones or RSS feeds. We believe there is a real demand from
users for all kind of information and especially sensing data. This
paper proposes a new network based service called Sensing Data Market
(SenseMart). The defining characteristic of SenseMart is that users
share their sensing data among themselves. In other words, SenseMart
facilitates the exchange (in the sense of a marketplace) of sensing data
and can be viewed as the "Napster" of sensing data. This paper discusses
possible architectures for SenseMart and the research challenges to
realise it. |
| 0702 |
WS-Policy4MASC Version 0.8 |
Vladimir Tosic, Abdelkarim Erradi, Piyush Maheshwari
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia |
WS-Policy4MASC is a new XML language that we have developed for policy specification in the Manageable and Adaptable Service Compositions (MASC) middleware. It can be also used for other Web service middleware. It extends the Web Services Policy Framework (WS-Policy) by defining new types of policy assertions. Goal policy assertions specify requirements and guarantees (e.g., maximal response time) to be met in desired normal operation. They guide monitoring activities in MASC. Action policy assertions specify actions to be taken if certain conditions are met or not met (e.g., some guarantees were not satisfied). They guide adaptation and other control actions. Utility policy assertions specify monetary values assigned to particular situations (e.g., execution of some action). They can be used by MASC for billing and for selection between alternative action policy assertions. Meta-policy assertions can be used to specify which action policy assertions are alternative and which conflict resolution strategy (e.g., profit maximization) should be used. In addition to these 4 new types of policy assertions, WS-Policy4MASC enables specification of additional information that is necessary for run-time policy-driven management. This includes information about conditions when policy assertions are evaluated/ executed, parties performing this evaluation /execution, a party responsible for meeting a goal policy assertion, ontological meaning, monitored data items, states, state transitions, schedules, events, and various expressions.
This research report provides technical details about WS-Policy4MASC solutions. First, we summarize the need for the language. Then, we list the requirements we have identified for a policy language to support middleware for QoS-aware and adaptive Web service composition. Then, we explain and discuss many architectural decisions in the language. They are illustrated with diagrams (XmlSpy diagrams of XML Schemas and UML diagrams) and examples. The Appendices contain XML files of detailed examples and XML schemas of the WS-Policy4MASC language grammar. |
| 0701 |
AC-Index: An Efficient Adaptive Index for Branching XML Queries |
Bo Zhang (^1), Wei Wang (^2), Xiaoling Wang (^1) and Aoying Zhou
1. Department of Computer Science and Engineering
Fudan University
Shanghai 200433, P. R. China
E-mail: {zhangbo, wxling, ayzhou}@fudan.edu.cn
2. School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: weiw@cse.unsw.edu.au |
Query-adaptive XML indexing has been proposed and shown to be an
efficient way to accelerate XML query processing, because it
dynamically adapts to the workload. However, existing adaptive index
suffers from a number of issues, such as lack of support for general
types of XML queries, and unsatisfactory query and update
performances. In this paper, we propose a new query-adaptive index
named AC-Index. It is designed to supports XML path queries with
branching predicates. We propose efficient index construction, query
processing, and index adaptation algorithms for the AC-Index,
together with a number of optimizations to further boost the
performance of the index. Our experimental results demonstrate that
the AC-Index significantly outperformed previous approaches in terms
of query processing and adaptation efficiencies. |
| 0625 |
Protocol Compatibility and Converter Synthesis |
Karin Avnit
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: kavnit@cse.unsw.edu.au
Vijay D'Silva
Department of Computer Science,
ETH Zurich
CH-8092 Zurich, Bwitzerland
E-mail: vdsilva@inf.ethz.ch
Arcot Sowmya
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sowmya@cse.unsw.edu.au
S. Ramesh
Department of Computer Science and Engineering
Indian Institute of Technology Poway, Bombay 400 076
E-mail: ramesh@cse.iitb.ac.in
Sri Parameswaran
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: sridevan@cse.unsw.edu.au |
With increasing complexity of chip architecture and growing pressure for short
time to market, hardware module reuse is common practice. However, in the
absence of module interface standards, use of pre-designed modules in a "plug
and play" fashion usually requires a mediator between mismatched interface
protocols. Though several approaches to such mediation have been proposed,
automation of protocol converter synthesis is yet to be realized. In this
work we focus on the framework of state based protocol models. We present a
formalism for modeling bus based communication protocols, the notion of
compatibility and a protocol converter. Using this formalism, we provide
algorithms for checking compatibility and demonstrate the process of automatic
converter synthesis for commercial bus protocols. |
| 0624 |
System F with Type Equality Coercions |
Martin Sulzmann
National University of Singapore
Email: sulzmann@comp.nus.edu.sg
Manuel M. T. Chakravarty
Computer Science and Engineering
University of New South Wales
Email: chak@cse.unsw.edu.au
Simon Peyton Jones and Kevin Donnelly
Microsoft Research Ltd
Cambridge, England
Email: {simonpj,t-kevind}@microsoft.com |
We introduce System FC, which extends System F with support for
non-syntactic type equality. There are two main extensions: (i) explicit
witnesses for type equalities, and (ii) open, non-parametric type functions,
given meaning by top-level equality axioms. Unlike System F, FC is
expressive enough to serve as a target for several different
source-language features, including Haskell's \code{newtype}, generalised
algebraic data types, associated types, functional dependencies, and
perhaps more besides. |
| 0623 |
A Framework for Protocol Discovery from Real-World Service
Conversation Logs |
Hamid Reza Motahari-Nezhad, R´egis Saint-Paul, Boualem Benatallah
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
Fabio Casati
University of Trento
Trento, Italy |
Understanding the business (interaction) protocol supported by a service
is very important for both clients and service providers: it allows
developers to know how to write clients that interact with a service, and
it allows development tools and runtime middleware to deliver
functionality that simplifies the service development lifecycle. It also
greatly facilitates the monitoring, visualization, and aggregation
of interaction data.
This paper presents a framework for discovering protocol definitions from
realworld service interaction logs. It first describes the challenges in
protocol discovery in such a context. Then, it presents a novel discovery
approach, which is widely applicable, robust to different kinds of
imperfections often present in real-world service logs, and helps to
derive protocols of small sizes, thanks to heuristics. As finding the most
precise and the smallest model is algorithmically not feasible from
imperfect service logs, finally, the paper presents an approach to refine
the discovered protocol via user interaction, to compensate for possible
imprecision introduced in the discovered model. The approach has been
implemented and experimental results show its viability on both synthetic
and real-world datasets. |
| 0622 |
Securing Channel Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks |
Aftabul Haq, Anjum Naveed and Salil Kanhere
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {ahaq,anaveed,salilk}@cse.unsw.edu.au |
In order to fully exploit the aggregate bandwidth available in
the radio spectrum, future Wireless Mesh Networks (WMN) are expected
to take advantage of multiple orthogonal channels, where the nodes
have the ability to communicate with multiple neighbours
simultaneously using multiple radios (NICs) over orthogonal
channels. Dynamic channel assignment is critical for ensuring
effective utilization of the non-overlapping channels. Several
algorithms have been proposed in recent years, which aim at
achieving this. However, all these schemes inherently assume that
the mesh nodes are well-behaved without any malicious intentions. A
recent work has exposed the vulnerabilities in channel assignment
algorithms. In this paper, a mechanism is proposed to secure the
channel assignment algorithms, addressing the security
vulnerabilities in the existing algorithms. The proposed mechanism
successfully prevents the WMN from the recently exposed attacks. The
simulation based experiments show the effectiveness of the proposed
solution. The experiments also show that the incurred overhead
because of security is negligible. |
| 0620 |
Patterns and the B Method: Bridging Formal and Informal Development |
Edward Chan
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: ekfchan@gmail.com
Brett Welch
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: brett.welch@gmail.com
Ken Robinson
School of Computer Science and Engineering
University of New South Wales
NSW 2052, Australia
E-mail: k.robinson@unsw.edu.au |
In a world increasingly dependent on software controlled systems,
the need for the verification of software safety and correctness has
never been greater. Traditional software development methods leave
much to be desired in this aspect, relying heavily on testing which
can be costly and time inefficient. A more efficient and less error
prone approach is to use formal methods, in particular the
B method, to develop software.
This thesis explores concepts and methods to assist developers in
using formal methods by borrowing concepts from the Object Oriented
world of software development. Previous attempts at doing this have
attempted to adapt the B method to the Object Oriented
paradigm. This thesis presents an alternative approach that adapts
concepts borrowed from the Object Oriented paradigm, to the B
method. By concentrating on commonly occurring patterns in
software development and drawing inspiration from the traditional
Gang of Four design patterns, this thesis presents a series of
patterns adapted to and specialised for the B method, demonstrating
how the beginnings of complex and significant systems can be
modelled in B. |
| 0619 |
Energy Driven Application Self-Adaptation at Run-time |
Jorgen Peddersen and Sri Parameswaran
School of Computer Science and Engineering
National ICT Australia
University of New South Wales
Sydney 2052 Australia
E-mail: {jorgenp, sridevan}@cse.unsw.edu.au |
Until recently, there has been a lack of methods to trade-off energy use for
quality of service at run-time in stand-alone embedded systems. Such systems
are motivated by the need to increase the apparent available battery energy
of portable devices, with minimal compromise in quality. The available
systems either drew too much power or added considerable overheads due to
task swapping. In this paper we demonstrate a feasible method to perform
these trade-offs. This work has been enabled by a low-impact power/energy
estimating processor which utilizes counters to estimate power and energy
consumption at run-time. Techniques are shown that modify multimedia
applications to differ the fidelity of their output to optimize the
energy/quality trade-off. Two adaptation algorithms are applied to multimedia
applications demonstrating the efficacy of the method. The method increases
code size by 1% and execution time by 0.02%, yet is able to produce an output
which is acceptable and processes up to double the number of frames. |
| 0618 |
CLIPPER: Counter-based Low Impact Processor Power Estimation at Run-time |
Jorgen Peddersen and Sri Parameswaran
School of Computer Science and Engineering
National ICT Australia
University of New South Wales
Sydney 2052 Australia
E-mail: {jorgenp, sridevan}@cse.unsw.edu.au |
Numerous dynamic power management techniques have been proposed
which utilize the knowledge of processor power/energy consumption at run-time.
So far, no efficient method to provide run-time power/energy data has
been presented. Current measurement systems draw too much power to be
used in small embedded designs and existing performance counters can not
provide sufficient information for run-time optimization. This paper presents
a novel methodology to solve the problem of run-time power optimization
by designing a processor that estimates its own power/energy consumption.
Estimation is performed by the addition of small counters that tally events
which consume power. This methodology has been applied to an existing
processor resulting in an average power error of 2% and energy estimation
error of 1.5%. The system adds little impact to the design, with only a 4.9%
increase in chip area and a 3% increase in average power consumption. A
case study of an application that utilizes the processor showcases the benefits
the methodology enables in dynamic power optimization. |
| 0617 |
Modeling Path Length in Wireless Ad-hoc Network |
Quan Jun Chen, Salil S. Kanhere, Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: {quanc, salilk, mahbub}@cse.unsw.edu.au |
Path length(i.e: the number of hops), the fundamental metric of
multi-hop wireless network, has a determinative effect on the
performance of wireless network, such as throughput, end-to-end delay
and energy consumption. In this paper, we propose a stochastic process
based mathematical model to analyze the shortest path length. The
model is based on the observation that greedy forwarding in geographic
routing can approximately find the shortest path in reasonably dense
network. We present formula for the probability mass function of path
length, given the distance between source and destination. In
addition, we also propose a simple but efficient formula to estimate
the mean path length. Our analytical results are well justified by a
rich set of simulations, in which both random and realistic mobility
scenarios have been investigated. |
| 0615 |
GOLD: An Overlay Multicast Tree with Globally Optimized Latency and Out-Degree |
Jun Guo, Sanjay Jha
School of Computer Science and Engineering
The University of New South Wales, Australia
Email: {jguo,sjha}@cse.unsw.edu.au
Suman Banerjee
Department of Computer Sciences
University of Wisconsin-Madison, USA
Email: suman@cs.wisc.edu |
End-to-end delay and interface bandwidth usage are two important performance
metrics in overlay multicast networks. This paper demonstrates that, by
jointly optimizing the placement of multicast service nodes and the routing
strategy for overlay multicast networks, it is possible to find an overlay
multicast tree that both minimizes the maximum end-to-end delay between the
source and the destinations, and balances the interface bandwidth usage
within the set of multicast service nodes. Motivated by this important
observation, we propose in this paper a joint optimization problem for
overlay mutlicast networks, where we wish to find a globally optimized
overlay multicast tree with minimum average end-to-end delay subject to two
stringent constraints: 1) The maximum end-to-end delay is bounded by the
unicast latency from the source to the farthest destination in the physical
topology; 2) The interface bandwidth usage is balanced within the set of
multicast service nodes. This problem is shown to be NP-hard. We present
a low complexity greedy algorithm that obtains good quality approximate
solutions to the problem. We further show how the greedy algorithm enables
the design of a weight-coded genetic algorithm that achieves closer-to-optimal
solutions with reasonable computational complexity. |
| 0614 |
System F with Type Equality Coercions (superseded by TR 0624) |
Martin Sulzmann
National University of Singapore
Email: sulzmann@comp.nus.edu.sg
Manuel M. T. Chakravarty
Computer Science and Engineering
University of New South Wales
Email: chak@cse.unsw.edu.au
Simon Peyton Jones and Kevin Donnelly
Microsoft Research Ltd
Cambridge, England
Email: {simonpj,t-kevind}@microsoft.com |
We introduce System FC, which extends System F with support for
non-syntactic type equality. There are two main extensions: (i) explicit
witnesses for type equalities, and (ii) non-parametric type functions,
given meaning by top-level equality axioms. Unlike System F, FC is
expressive enough to serve as a target for several different
source-language features, including Haskell's newtype, generalised
algebraic data types, associated types, functional dependencies, and
perhaps more besides. FC can therefore serve as a typed intermediate
language in a compiler that supports these features. |
| 0613 |
An Interim Report of XML Process Models |
Tu Tak Tran
School of Computer Science and Engineering
University of New South Wales
Sydney NSW 2052 Australia
Email: ttt@cse.unsw.edu.au |
This report presents preliminary models for XML processes, and a general framework for its usage. The set of models are at an early stage of development and are not as yet complete. This report serves as an interim for further development in XML process modeling. |
| 0611 |
A Graph Drawing Approach to Sensor Network Localization |
Muhammad S. Nawaz and Sanjay K. Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {mnawaz,sjha}@cse.unsw.edu.au |
In this work, we present a centralized localization mechanism for
wireless sensor networks. Our method is based on a graph drawing
algorithm and utilizes inter node distances to localize sensor nodes
in a local coordinate system upto a global translation, rotation and
reflection without any absolute reference positions such as GPS or
other anchor nodes. We show through simulations that, it is possible
to avoid folds and flips in the localized network layout if the entire
topology is considered as a whole as opposed to distances to immediate
neighbors only. We assess the effect of different parameters like
scale, node degree and ranging noise on our algorithm. Finally, we
propose a hierarchical approach to make the algorithm scalable for
large networks, which we would like to pursue as future work. |
| 0610 |
Patching Approximate Solutions in Reinforcement Learning |
Min Sub Kim
ARC Centre of Excellence for Autonomous Systems
School of Computer Science and Engineering
University of New South Wales
Sydney NSW 2052 Australia
msk@cse.unsw.edu.au
William Uther
National ICT Australia
Sydney NSW 2052 Australia
william.uther@nicta.com.au |
This report introduces an approach to improving an approximate solution in
reinforcement learning by augmenting it with a small overriding patch.
Many approximate solutions are smaller and easier to produce than a flat
solution, but the best solution within the constraints of the
approximation may fall well short of global optimality. We present an
algorithm for efficiently learning a small patch to reduce this gap.
Empirical evaluation demonstrates the effectiveness of patching, producing
combined solutions that are much closer to global optimality. |
| 0609 |
On building 3D maps using a Range Camera:
Applications to Rescue Robotics |
Raymond Sheh, M. Waleed Kadous and Claude Sammut
ARC Centre of Excellence for Autonomous Systems
School of Computer Science and Engineering
The University of New South Wales
Sydney, NSW, 2052, Australia
[rsheh|waleed|claude]@cse.unsw.edu.au |
It is critical in many mobile robotics applications to characterise
the presence and position of objects around the robot. This is the
case whether the mobile robot is under autonomous or teleoperative
control.
In this paper, we examine the use of a CSEM SwissRanger SR-2 3D range
camera which allows the generation of dense, accurate 3D point clouds
around a mobile robot. Combined with other data sources, such as video
cameras, this allows the creation of 3D maps that can be used for .fly
throughs.. Furthermore, this same technique allows a teleoperator to
very accurately place landmarks within the 3D maps.
As this device is still somewhat prototypical, we also discuss some of
the issues associated with the use of this device. The test application was
the 2005 RoboCup Rescue Robot League, a competition that simulates
robot-assisted Urban Search and Rescue (USAR) tasks and places great
importance on effectively generating maps.
Novel techniques for processing the raw measurements from the sensor,
and its use to create maps of mock disaster sites are discussed. The
maps generated, part of Team CASualty.s entry, were received very well
by the judges of the competition and were unique in their combination
of 3D, colour and thermal information, and the automated way in which
the placement of landmarks and other annotations were performed. The
maps were instrumental in the team.s achievement of 3rd place. |
| 0608 |
Minimum Latency Broadcasting in Multi-Radio Multi- Channel Multi-Rate Wireless Mesh Networks |
Junaid Qadir, Chun Tung Chou, Archan Misra*
School of Computer Science and Engineering, University of New South Wales, Australia
IBM T J Watson Research Center, Hawthorne, New York, USA*
Email: {junaidq, ctchou}@cse.unsw.edu.au,archan@us.ibm.com |
We address the problem of minimizing the worst-case broadcast delay in
multi-radio multi-channel multi-rate (MR2-MC) wireless mesh networks
(WMN). The problem of `efficient' broadcast in such networks is
especially challenging due to the numerous inter-related decisions
that have to be made. The multi-rate transmission capability of WMN
nodes, interference between wireless transmissions, and the hardness
of optimal channel assignment adds complexity to our considered
problem. We present four heuristic algorithms to solve the minimum
latency broadcast problem for such settings and show that the `best'
performing algorithms usually adapt themselves to the available radio
interfaces and channels. We also study the effect of channel
assignment on broadcast performance and show that channel assignment
can affect the broadcast performance substantially. More importantly,
we show that a channel assignment that performs well for unicast does
not necessarily perform well for broadcast/multicast. To the best of
our knowledge, this work constitutes the first contribution in the
area of broadcast routing for MR2-MC WMN. |
| 0607 |
Security Vulnerabilities in Channel Assignment of Multi-Radio Multi-Channel Wireless Mesh Networks |
Anjum Naveed and Salil Kanhere
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {anaveed,salilk}@cse.unsw.edu.au |
In order to fully exploit the aggregate bandwidth available in
the radio spectrum, future Wireless Mesh Networks (WMN) are expected
to take advantage of multiple orthogonal channels, with nodes having
the ability to communicate with multiple neighbors simultaneously
using multiple radios (NICs) over orthogonal channels. Dynamic
channel assignment is critical for ensuring effective utilization of
the non-overlapping channels. Several algorithms have been proposed
in recent years, which aim at achieving this. However, all these
schemes inherently assume that the mesh nodes are well-behaved
without any malicious intentions. In this report, we expose the
vulnerabilities in channel assignment algorithms and unveil three
new security attacks: Network Endo-Parasite Attack (NEPA), Channel
Ecto-Parasite Attack (CEPA) and low-cost ripple effect attack
(LORA). These attacks can be launched with relative ease by a
malicious node and can cause significant degradation in the network
performance. We also evaluate the effectiveness of these attacks
through simulation based experiments and briefly discuss possible
solutions to counter these new threats. |
| 0606 |
Piggy Back Challenge Based Security Mechanism for IEEE 802.11i Wireless LAN CCMP Protocol |
M. Junaid Hussain , M. Akbar, Muid Mufti & Salil Kanhere
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: junaid-mcs@nust.edu.pk , makber59@hotmail.com , muid@uetaxila.edu.pk, salilk@cse.unsw.edu.au |
Counter mode is used for data confidentiality within IEEE 802.11
Wireless LANs. Counter mode utilizes temporal key and counter value
for encryption . The temporal key is derived as a result of successful
authentication. It is shown in this paper that Counter mode is
vulnerable to attacks by intruders. This paper presents a piggy back
challenge based security mechanism. It is shown that the nonce and
initial counter are derived from the session key and are kept
secret. The same nonce is used as a challenge text from authenticator
to supplicant. The supplicant utilizes the nonce as encryption key for
the subsequent packets. The proposed challenge response mechanism is a
continuous process and thus provides freshness, per packet encryption
key and unpredictability of counter value. The freshness provides
protection against replay attacks, the unpredictability of counter
value prevents precomputation attack and the per-packet challenge
response mechanism using separate encryption key for each packet
strengthens the security of the connection against unauthorized access
by immediately discarding the packet if Per-Packet Authentication
fails. Our piggy back challenge based Security mechanism provides a
fundamental base for strengthening the security of WLAN. |
| 0605 |
Lock Selection in Practice |
Abdelsalam Shanneb and John Potter
{shanneba,potter}@cse.unsw.edu.au
Programming Languages and Compilers Group
School of Computer Science and Engineering
The University of New South Wales
Sydney, NSW 2052, Australia |
This report is a continuation of our last report (UNSW-CSE-TR-604).
Here, we present our algorithm for offering lock choices. We show all
the details involved in making lock choices for programmers. We offer
different approaches to lock selection; we propose top-down and
bottom-up strategies, as well as, additive and subtractive techniques.
These lock choices are based on the previously established Galois
connection between the layers of a composite. We also present several
examples that demonstrate our prototype tool for lock selection, the
output of which is in Appendix A. |
| 0604 |
A Galois Connection in Composite Objects |
Abdelsalam Shanneb and John Potter
{shanneba,potter}@cse.unsw.edu.au
Programming Languages and Compilers Group
School of Computer Science and Engineering
The University of New South Wales
Sydney, NSW 2052, Australia |
With the advent of multiprocessors on the desktop, software
applications are increasingly likely to adopt multithreaded
architectures. To cope with the complexity of concurrent systems,
programmers build systems from thread-safe components. This produces
excessive and redundant locking, restricting the potential for
concurrency within the system.
Rather than deploying individual thread-safe components, we advocate
deferring the deployment of locks until the code dependencies are
known. This avoids redundant locking, and allows the granularity of
concurrency to be chosen in a flexible way. In earlier work we
identified a formal relationship, known as a Galois connection,
between the potential for concurrency in a composite system and the
locking requirements for its components.
This report highlights the role of fixpoints for lock selection.
The subsequent report (UNSW-CSE-TR-605) will investigate strategies
for selecting locks in a composite system. |
| 0603 |
COMMA: A Communications Methodology for
Dynamic Module-based Reconfiguration of FPGAs |
Shannon Koh and Oliver Diessel
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: shannonk@cse.unsw.edu.au and odiessel@cse.unsw.edu.au |
On-going improvements in the scaling of FPGA device sizes and
time-to-market pressures motivate the adoption of a module-oriented
design flow for the development of applications. At the same time,
economic factors encourage the reuse of smaller devices for high
performance computational tasks. Like other researchers, we therefore
envisage a need for dynamic reconfiguration of FPGAs at the module level.
However, proposals to date have not focussed on communications issues,
have advocated use of specific protocols, cannot be readily implemented,
and/or do not support current device architectures. This paper proposes
a methodology for the rapid deployment of a communications infrastructure
that efficiently supports the communications needs of a collection of
dynamic modules when these are known at design time. The methodology also
provides a degree of flexibility to allow a range of unknown communication
requirements to be met at run time. Our aim is to support new tiled
dynamically reconfigurable architectures such as Virtex-4, as well as
mature device families. We assess a prototype of the communications
infrastructure and outline opportunities for automating the design flow. |
| 0601 |
OCEAN -- Scalable and Adaptive Infrastructure for
On-board Information Access |
Boualem Benatallah, Mahbub Hassan, Lavy Libman*, Aixin Sun
School of Computer Science and Engineering
University of New South Wales
Sydney, NSW 2052, Australia
Email: {boualem,mahbub,aixinsun}@cse.unsw.edu.au
*National ICT Australia
Bay 15, Australian Technology Park
Eveleigh, NSW 1430, Australia
Email: Lavy.Libman@nicta.com.au |
The idea of providing seamless connectivity and information access to
users on-board public transport vehicles has attracted increasing
popularity in recent years, as is evidenced by several commercially
available systems that have attempted to implement it. In this article,
we overview the specific technological challenges, research issues, as
well as opportunities, that arise in the context of providing communication
and information access on public transport. We focus on both the networking
perspective --- in particular, discussing extensions required to existing
TCP/IP mechanisms to support the moving on-board networks --- and the data
management perspective, e.g. personalization of information and
caching/pre-fetching for a highly dynamic and heterogeneous population
of users. We contend that, to offer the best performance and flexibility,
the design of public transport information systems ought to take advantage
of the synergy between these two areas. |
| 0524 |
Validation of SECI Model in Education |
Cat Kutay
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: ckutay@cse.unsw.edu.au
Aybuke Aurum
School of Information Systems, Technology and Management
University of New South Wales
Sydney 2052 Australia
E-mail: aybuke@unsw.edu.au |
The use of Knowledge Management (KM) is increasingly relevant to
education as our knowledge of factors influencing the effective
managing of information and knowledge resources. It is important that
educational organizations understand the application of strategies for
managing the knowledge resources and providing appropriate access to
this information within the University context. This article examines
data collected from students doing the Software Engineering Program at
UNSW. This data is used to analyse the industrial SECI model of KM as
applied to the educational domain. We are looking at the validity of
the empirical evidence. Results indicated that the data provided a
valid study of KM in this context. |
| 0523 |
Redback: A Low-Cost Advanced Mobility Robot |
Raymond Sheh
School of Computer Science and Engineering
and The National ICT Australia
University of New South Wales
Sydney 2052 Australia
E-mail: rsheh@cse.unsw.edu.au |
Many of the more interesting applications of mobile robotics involve robots
that are able to traverse unstructured environments. Unfortunately, currently
available robots for such a purpose tend to be limited in their mobility (very
few can climb stairs for instance), are excessively heavy, must be custom
built or are very expensive.
This article describes preliminary work on construction of an advanced
mobility robot based on a Tarantula radio controlled toy, sold by MGA
Entertainment. Despite being very low in cost (sub-$200AUD), this toy can
easily climb stairs and overcome obstacles that challenge much larger robots.
It can easily carry an onboard computer which can directly interface with the
existing motor controllers as well as additional cameras, small laser
rangefinders and other sensors.
The full cost of parts for the basic robot, including computer and simple
sensors, is expected to be around the $1,000AUD mark with basic computer-less
versions starting below $300AUD. The modified robot has been dubbed Redback,
after the Australian spider of the same name. |
| 0522 |
The Shadow Knows: Refinement of ignorance in sequential programming |
Carroll Morgan
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: carrollm@cse.unsw.edu.au |
Sequential-program state can be separated into "visible" and "hidden" parts in
order to allow knowledge-based reasoning about the hidden values.
Ignorance-preserving refinement should ensure that observing the visible part of
an implementation can reveal no more about the hidden part than could be
revealed by its specification.
Possible applications are zero-knowledge protocols, or security contexts where
the "high-security" state is considered hidden and the "low-security" state is
considered visible.
Rather than checking for ignorance preservation at each stage, we suggest
program-algebraic "refinement rules" that preserve ignorance by construction.
The Dining Cryptographers is a motivating example, in which ignorance of certain
variables (coins) is intended to contribute to an ignorance property of the
overall protocol. Our algebra is powerful enough to derive the Dining
Cryptographers' Protocol, while retaining soundness by avoiding (for example)
the Refinement Paradox.
We formulate and justify general principles about which refinement rules should
be retained, for algebraic power and utility, and which should be discarded, for
soundness. |
| 0521 |
ASEHA: A Web Services Protocol Modelling Formalism |
Pemadeep Ramsokul and Arcot Sowmya
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
and
National ICT Australia(NICTA)
Locked Bag 6016, NSW 1466, Australia
E-mail: {pkramsok, sowmya}@cse.unsw.edu.au |
Agents require standard and reliable protocols to interact with different
service providers in order to provide high quality service to customers over
the web. Many useful protocols are coming into the market, but are
ambiguously specified by protocol designers and without being fully verified.
These can lead to interoperabilty problems among implementations of same
protocol and high software maintenance costs.
In this paper, we propose a hierarchical automata-based framework to model
the necessary features of protocols to verify their correctness. Our experience
shows that the graphical models produced, provide invaluable insights and
can be used to complement specifications to drastically reduce, if not eliminate,
ambiguities. We illustrate our formalism with a version of the
WS-AtomicTransaction protocol. |
| 0520 |
Formal Methods in the Enhancement of the Data Security Protocols of Mobile Agents |
Raja Al-Jaljouli
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: rjaljoli@cse.unsw.edu.au |
The security of data gathered by mobile agents is crucial to the
success of e-commerce and formal methods play an important role in the
verification of the data security protocols. This paper demonstrates
the effectiveness of formal methods in the analysis and design of
security protocols. In this paper, we implement a formal method in the
analysis and the rectification of a recent mobile agent security
protocol by Maggi and Sisto [14] named "Configurable Mobile Agent Data
Protection Protocol". We use STA (Symbolic Trace Analyzer), a formal
verification tool that is based on symbolic techniques, in the
analysis of the protocol. The analysis revealed a flaw in the security
protocol. An adversary can impersonate the genuine initiator, and thus
can breach the privacy of the gathered data. The protocol does not
detect the malicious act. In addition [14] states that the protocol
does not achieve strong data integrity in case two hosts conspire or a
malicious host is visited twice. We rectify the protocol so it
prevents the malicious acts, and then use STA tool to analyze a
reasonably small instance of the protocol in key configurations. The
analysis shows that the repaired protocol is free of flaws. Moreover,
we reason about the security of a general model of the repaired
protocol. To our knowledge, we are the first to repair the protocol,
and analyze it formally. |
| 0519 |
Adaptive Position Update in Geographic Routing |
Quan Jun Chen, Salil S. Kanhere, Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: {quanc, salilk, mahbub}@cse.unsw.edu.au
Kun-Chan Lan
National ICT Australia, Sydney, Australia,
E-mail: Kun-Chan.Lan@nicta.com.au |
In geographic routing, nodes need to maintain up-to-date positions of
their immediate neighbours for making effective forwarding
decisions. Periodic broadcasting of beacon packets that contain the
geographic location coordinates of the nodes is a popular method used
by most geographic routing protocols to maintain neighbour
positions. We contend that periodic beaconing regardless of network
mobility and traffic pattern does not make optimal ulilisation of the
wireless medium and node energy. For example, if the beacon interval
is too small compared to the rate at which a node changes its current
position, periodic beaconing will create many redundant position
updates. Similarly, when only a few nodes in a large network are
involved in data forwarding, resources spent by all other nodes in
maintaining their neighbour positions are greatly wasted. To address
these problems, we propose the Adaptive Position Update (APU) strategy
for geographic routing. Based on mobility prediction, APU enables
nodes to update their position adaptively to the node mobility and
traffic pattern. We embed APU into the well known Greedy Perimeter
Stateless Routing Protocol (GPSR), and compare it with original GPSR
in the ns-2 simulation platform. We conducted several experiments with
randomly generated network topologies and mobility patterns. The
results confirm that APU significantly reduces beacon overhead without
having any noticeable impact on the data throughput of the
network. This result is further validated through a trace driven
simulation of a practical vehicular ad-hoc network topology that
exhibits realistic movement patterns of public transport buses in a
metropolitan city. |
| 0518 |
Reducing File Download Delay by QoS Driven Parallelization of Resources. |
Shaleeza Sohail, Sanjay Jha, Salil S. Kanhere and Chun Tung Chou
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: (sohails,sjha,salilk,ctchou)@cse.unsw.edu.au |
In this paper, we propose a novel approach, for reducing the download
time of large files over the Internet. Our approach, known as
Parallelized File Transport Protocol (P-FTP), proposes simultaneous
downloads of disjoint file portions from multiple file servers. P-FTP
server selects file servers for requesting client, on the basis of a
variety of QoS parameters, such as, available bandwidth and server
utilisation. The sensitivity analysis of our file server selection
technique shows that it performs significantly better than random
selection. The scalability study of P-FTP server shows that it can
handle queries of large number of P-FTP clients, without becoming
bottleneck. During the file transfer, P-FTP client monitors the file
transfer flows to detect slow servers and congested links and adjusts
the file distributions accordingly. P-FTP is evaluated with
simulations and real-world implementation. The results show at least
50% reduction in download time, when compared to the traditional
file-transfer approach. Moreover, we have also carried out a
simulation-based study to investigate the issues related to large
scale deployment of our approach on the Internet. Our results
demonstrate that large number of P-FTP users has no adverse effect on
the performance perceived by non P-FTP users. In addition, the file
servers and network are not significantly affected by large scale
deployment of P-FTP. |
| 0517 |
B-SCP: a requirements analysis framework for validating strategic
alignment of organizational IT based on strategy, context, and process |
Steven J. Bleistein, Karl Cox, June Verner
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: stevenb@cse.unsw.edu.au
Keith T. Phalp
Empirical Software Engineering Research Group
Bournemouth University, United Kingdom |
Ensuring that organizational IT is in alignment with and provides
support for an organization's business strategy is critical to
business success. Despite this, business strategy and strategic
alignment issues are all but ignored in the requirements engineering
research literature. We present B-SCP, a requirements engineering
framework for organizational IT that directly addresses an
organization's business strategy and the alignment of IT requirements
with that strategy. B-SCP integrates the three themes of strategy,
context, and process using a requirements engineering notation for
each theme. We demonstrate a means of cross-referencing and
integrating the notations with each other, enabling explicit
traceability between business processes and business strategy. In
addition, we show a means of defining requirements problem scope by
applying a business modeling framework as a Jackson problem
diagram. Our approach is illustrated via application to an
exemplar. The case example demonstrates the feasibility of B-SCP, and
we present a comparison with other approaches. |
| 0516 |
A Competitive Learning Algorithm for Checking Sensor Data Integrity in Unknown Environments |
Tatiana Bokareva.
School of Computer Science and Engineering.
The University of NSW.
tbokareva@cse.unsw.edu.au
Nirupama Bulusu.
School of Computer Science.
Portland State University.
nbulusu@cs.pdx.edu
Sanjay Jha.
School of Computer Science and Engineering.
The University of NSW.
sjha@cse.unsw.edu.au |
Ad-Hoc wireless sensor networks derive much of their promise from
their potential for autonomously monitoring remote or physically
inaccessible locations. As we begin to deploy sensor networks in real
world applications, ensuring the integrity of sensor data is of
paramount importance.
In this paper, we motivate, propose, evaluate and analyze an online
algorithm for modeling and validating sensor data in an unknown
physical environment. Previous work on checking sensor data integrity
developed within the context of process control systems uses a priori
characterization of sensor data. In contrast, our approach leverages
the concept of competitive learning for online characterization of a
dynamic, unknown environment and the derivation of conditions for
verifying sensor data integrity over time. Moreover, to scale to very
large sensor networks, our algorithm leverages in-network processing a
hierarchical, tiered sensor network by executing on the distributed
cluster heads, rather than at a central base station.
We prove the convergence properties of our algorithm through
theoretical analysis. Furthermore, we implement our algorithm on a
real physical sensor network of motes and Stargates, and demonstrate
that our algorithm successfully learns real-world environmental data
characteristics and filters anomalous data in a sensor network. |
| 0515 |
A Dynamic Caching Algorithm Based on Internal Popularity Distribution of Streaming Media |
Jiang Yu,
Dept. of Electronics and Information Engineering, Huazhong University of Science & Technology, China
frankyu@263.net
Chun Tung Chou
School of Computer Science and Engineering, University of New South Wales, Australia
ctchou@cse.unsw.edu.au |
Most proxy caches for streaming videos do not cache the entire video
but only a portion of it. This is partly due to the large size of
video objects. Another reason is that the popularity of different part
of a video can be different, e.g. the prefix is generally more
popular. Therefore, the development of efficient cache mechanisms
requires an understanding of the internal popularity characteristics
of streaming videos. This paper has two major contributions. Firstly,
we analyze two 6-month long traces of RTSP video requests recorded at
different streaming video servers of an entertainment video-on-demand
provider, and show that the traces provide evidence that the internal
popularity of the majority of the most popular videos obeys a
$k$-transformed Zipf-like distribution. Secondly, we propose a caching
algorithm which exploits this empirical internal popularity
distribution. We find that this algorithm has similar performance
compare with fine-grained caching but requires significantly less
state information. |
| 0514 |
Low Latency Broadcast in Multi-Rate Wireless Mesh Networks |
Chun Tung Chou
School of Computer Science and Engineering,
University of New South Wales, Australia
ctchou@cse.unsw.edu.au
Archan Misra
IBM T J Watson Research Center,
Hawthorne, New York, USA
archan@us.ibm.com
Junaid Qadir
School of Computer Science and Engineering,
University of New South Wales, Australia
junaidq@cse.unsw.edu.au |
In a multi-rate wireless network, a node can dynamically adjust its
link transmission rate by switching between different modulation
schemes. For the current IEEE802.11a/b/g standards, this rate
adjustment is limited to unicast traffic. In this paper, we consider a
novel type of multi-rate mesh networks where a node can dynamically
adjust its link layer multicast rates to its neighbours. In
particular, we consider the problem of realising low latency
network-wide broadcast in this type of multi-rate wireless meshes. We
will first show that the multi-rate broadcast problem is significantly
different from the single-rate case. We will then present two
algorithms for achieving low latency broadcast in a multi-rate mesh
which exploits both wireless broadcast advantage and the multi-rate
nature of the network. Simulations based on current 802.11 parameters
show that multi-rate multicast can reduce broadcast latency by 3--6
times compared with using the lowest rate alone. In addition, we show
the significance of the product of transmission rate and transmission
coverage area in designing multi-rate wireless mesh networks for
broadcast. |
| 0513 |
Toward a Framework for Capturing and Using Architecture Knowledge |
Muhammad Ali Babar, Ian Gorton, Ross Jeffery
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {malibaba, iango, rossj}@cse.unsw.edu.au |
Management of architecture knowledge is vital for improving an
organization's architectural capabilities. Despite the recognition of
the importance of capturing and reusing architecture knowledge, there
is no suitable support mechanism. We propose a conceptual framework
for providing appropriate guidance and tool support for making tacit
or informally described architecture knowledge explicit. This
framework identifies different approaches to capturing implicit
architecture knowledge. We discuss different usages of the captured
knowledge to improve the effectiveness of architecting process. The
report also presents a brief description of a prototype of a web-based
architecture knowledge management tool to support the storage and
retrieval of the captured knowledge. The report concludes with open
issues that we plan to address in order to successfully transfer this
support mechanism for capturing and using architecture knowledge to
the industry. |
| 0511 |
Secure Untrusted Binaries --- Provably! |
Simon Winwood, Manuel M. T. Chakravarty
University of New South Wales and
National ICT Australia
E-mail: {sjw, chak}@cse.unsw.edu.au |
A standard method for securing untrusted code is code rewriting,
whereby operations that might compromise a safety policy are secured
by additional dynamic checks. In this paper, we propose a novel
approach to sandboxing that is based on a combination of code
rewriting and hardware-based memory protection. In contrast to
previous work, we perform rewriting on raw binary code and provide a
machine-checkable proof of safety that includes the interaction of the
untrusted binary with the operating system. This proof constitutes a
crucial step towards the use of rewritten binaries with proof-carrying
code. |
| 0510 |
A Proposed Security Protocol for Data Gathering Mobile Agents |
Raja Al-Jaljouli
School of Computer Science and Engineering
University of New South Wales
Sydney 2052, Australia
E-mail: rjaljoli@cse.unsw.edu.au |
This paper addresses the security issue of the data which mobile
agents gather as they are traversing the Internet. Several
cryptographic protocols were presented in the literature asserting the
security of gathered data. The security is based on the implementation
of one or more of the following security technique: public key
encryption, digital signature, and message authentication code,
backward chaining, one-step forward chaining, and code-result
binding. Formal verification of the protocols reveals unforeseen
security flaws, such as truncation or alteration of the collected
data, breaching the privacy of the gathered data, sending others data
under the private key of a malicious host, and replacing the collected
data with data of similar agents. So the existing protocols are not
truly secure. In this paper, we present an accurate security protocol
[21] which aims to assert strong integrity, authenticity, and
confidentiality of the gathered data. The proposed protocol is derived
from the Multi-hops protocol [14], where the security relies on a
message authentication code, a chain of encapsulated offers, and a
chained hash of a random nonce. The Multi-hops protocol suffers from
security flaws, e.g. an adversary might truncate/ replace collected
data, or sign others data with his own private key without being
detected. The proposed protocol [21] refines the Multi-hops protocol
by implementing the following security techniques: utilization of
co-operating agents, scrambling the gathered offers, requesting a
visited host to clear its memory from any data acquired as a result of
executing the agent before the host dispatches the agent to the
succeeding host, carrying out verifications during the agent.s
lifecycle in addition to the verifications upon agent.s return to the
initiator. The verifications are on the identity of the genuine
initiator at the early execution of the agent at a visited host. The
proposed protocol also implements the common security techniques such
as public key encryption, digital signature, etc. The security
techniques implemented in the proposed protocol would rectify the
security flaws revealed in the existing protocols. We prove its
correctness by analyzing the security properties using STA [44, 45], a
finite-state verification tool. |
| 0509 |
A Configuration Memory Architecture for Fast FPGA Reconfiguration |
Usama Malik* and Oliver Diessel**
*Architecture Group
School of Computer Science and Engineering
University of New South Wales
Sydney 2052, Australia
**Embedded, Real-time, and Operating Systems (ERTOS) Program
National ICT Australia
Email: {umalik, odiessel}@cse.unsw.edu.au |
This report presents a configuration memory architecture that offers
fast FPGA reconfiguration. The underlying principle behind the design is
the use of fine-grained partial reconfiguration that allows significant
configuration re-use while switching from one circuit to another.
The proposed configuration memory works by reading on-chip configuration
data into a buffer, modifying them based on the externally supplied
data and writing them back to their original registers. A prototype
implementation of the proposed design in a 90nm cell library indicates
that the new memory adds less than 1% area to a commercially available
FPGA implemented using the same library. The proposed design reduces the
reconfiguration time for a wide set of benchmark circuits by 63%. However,
power consumption during reconfiguration increases by a factor of 2.5
because the read-modify-write strategy results in more switching in the
memory array. |
| 0508 |
Implementation of a Multihoming Agent for Mobile On-board Communication |
Jun Yao, Yi Duan, Jianyu Pan, Kun-chan Lan, Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {jyao713, ydua280, jpan122, klan, mahbub}@cse.unsw.edu.au |
The idea of using multiple access links (so called multihoming) is commonly used
to improve the aggregate bandwidth and the overall service availability, which
has been employed by large enterprises and data centers as a mechanism to extract
good performance and enhance the network reliability from their service providers
for a while. However, in the context of network mobility, because of the diversity
and unreliability of the wireless links, adaptable multihomed prototype supporting
mobile networks should be studied and implemented.
This report introduces us the details from the implementation project of a
multihoming agent, which is developed on a Linux based platform and allows router
to access and switch between multiple access links including WLAN and GPRS. The
prototype is capable of dynamically switching users' data traffic from one network
interface to another, i.e. Ethernet, WLAN, and GPRS, without breaking transport
layer sessions, based on the interfaces' status and policy in use. |
| 0507 |
Selectivity Estimation of Multidimensional Queries Based on Point Synthesis |
Matthew Gebski Raymond K. Wong
National ICT Australia and
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia |
An important problem in database systems is estimating the selectivity of
multidimensional queries. While various approaches have been proposed for
selectivity estimation for low dimensional spatial databases, many of these
techniques have weaknesses for higher dimensional data. This paper presents a
novel approach to estimate the selectivity of queries by generating points from
an empirical distribution and testing these against a given query. This allows
us to take small samples as a summary and generate points for selectivity
estimation. Unlike histogram based approaches, our technique does not use
containers to represent regions of the data. This alleviates problems that
arise when container densities approach zero as dimensionality increases.
Experiments show that our approach handles high levels of skew and very high
dimensionality, and achieves higher accuracy than previous approaches. |
| 0506 |
Rotated Library Sort |
Franky Lam, Raymond K. Wong
National ICT Australia and
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia |
This paper investigates how to improve the worst case runtime of
Insertion Sort while keeping it in-place, incremental and adaptive.
To sort an array of n elements with w bits for each element, classic
Insertion Sort runs in O(n^2) operations with wn bits space.
Gapped Insertion Sort has a runtime of O(n log n) with a high
probability of only using (1 + e)wn bits space. This paper shows
that Rotated Insertion Sort guarantees O(sqroot(n) log n)
operations per insertion and has a worst case sorting time of
O(n^(1.5) log n) operations by using optimal O(w) auxiliary bits.
By using extra Theta(sqroot(n) log n) bits and recursively applying
the same structure l times, it can be done with O(2^l n^(1 + 1/l))
operations. Apart from the space usage and time guarantees, it also
has the advantage of efficiently retrieving the i-th element in
constant time. This paper presents Rotated Library Sort that
combines the advantages of the above two improved approaches. |
| 0505 |
A Scheduler Architecture for INTEL's IXP2400 Network Processor |
Fariza Sabrina and Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia.
E-mail: {farizas, sjha}@cse.unsw.edu.au |
This report describes the design and implementation of a
scheduling algorithm called CBCS on network processors. The CBCS
algorithm is a fair and efficient resource scheduling algorithm
that can fairly allocate multiple resources among contending
flows. We have implemented this algorithm on Intel's IXP2400
network processor. The main objectives of implementing our
scheduling algorithms on a real world Attached Network Processor
(ANP) such as Intel IXP2400 Network processor were (1) to validate
that CBCS can be implemented on a highly scalable real world
programmable node or ANP for managing the CPU and bandwidth
resources, (2) to provide scheduling solutions that could be opted
or used by the ANP vendors like Intel to build and deliver
efficient building block(s) (as a part of their Software
Development Kit (SDK) or development framework) for resource
scheduling purposes. The experimental results from IXP2400
implementation demonstrate the effectiveness and high performance
of this algorithm in real world system. |
| 0504 |
Synthesis of Distributed Systems from Knowledge-Based Specifications |
Ron van der Meyden
School of Computer Science and Engineering,
University of New South Wales
National ICT Australia
&
Thomas Wilke
Institut für Informatik und Praktische Mathematik
Christian-Albrechts-Universität zu Kiel |
We consider the problem of synthesizing protocols in a distributed
setting satisfying specifications phrased in the logic of linear
time and knowledge. In general, synthesis in distributed settings
is undecidable already for linear-time temporal logic
specifications, but there exist special cases in which synthesis
from linear-time temporal logic specifications is known to be
decidable. On the basis of these results and a result on the
decidability of synthesis of temporal and knowledge specifications
in systems with a single agent, van der Meyden and Vardi [CONCUR 96]
conjectured that synthesis of temporal and knowledge specifications
would be decidable in two classes of environments: hierarchical
environments, in which each agent in a linear sequence observes at
least as much as the preceding agents, and broadcast environments,
in which all communication is constrained to be by synchronous
broadcast. We show that this conjecture is true in the case of
broadcast environments, but false in the case of even a very simple
type of hierarchical environment, where only two agents are
involved, one of which observes every aspect of the system state and
one of which observes nothing of it. Nevertheless, synthesis from
linear-time logic specifications is decidable in hierarchical
environments. Moreover, for specifications that are positive in the
knowledge modalities, the synthesis problem can be reduced to the
same problem for the logic of linear time. We use these facts to
conclude the decidability in hierarchical systems of a property
closely related to nondeducibility on strategies, a notion that has
been studied in computer security. |
| 0503 |
A Multi-Channel DS-CDMA Media Access Control Protocol for Wireless Sensor Networks |
Bao Hua Liu, Chun Tung Chou, Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia.
E-mail: {mliu, ctchou, sjha}@cse.unsw.edu.au |
This paper proposes a novel multi-channel media access control (MAC)
protocol for direct sequence code division multiple access (DS-CDMA)
wireless sensor network. Our protocol design uses combination of
DS-CDMA and frequency division to reduce the channel interference and
consequently improves system capacity and network throughput. We
provide theoretical characterization of the mean multiple access
interference (MAI) at a given node in relation to the number of
frequency channels. We show that by using only a small number of
frequency channels, the mean MAI can be reduced significantly. Through
discrete event simulation, we provide comparison of our proposed
system to a pure DS-CDMA system as well as a contention based
system. Simulation results reveal that our proposed system can achieve
15-20 times of system efficiency than a contention based system. When
same number of packets are transmitted in the network, our system
consumes only 10% of communication energy than the contention based
system. |
| 0442 |
IC2: An Interval based Characteristic Concept Learner |
Pramod K. Singh
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: pksingh@cse.unsw.edu.au |
In many real-world problems it can be argued that classification
based on characteristic descriptions delivers a more correct and
comprehensive concept than the existing discriminative descriptions.
Most classification algorithms suffer from an inability to detect
instances of classes which are not present in the training set. A
novel approach for characteristic concept rule learning called IC2
is proposed in this paper. It uses the descriptions of one class
objects for learning concept rules for the classification and
descrimination of unseen instances. In this approach interval-based
class characteristic rules are induced from the descriptions of the
labeled objects of a class. The paper illustrates the approach and presents
the empirical results obtained on some data sets of continuous feature
variables. The IC2 classifier is evaluated and its classification
accuracy is compared with a state-of-the-art characteristic concept
classification algorithm ID3-SD. |
| 0441 |
Creative Commons Speech Repository |
Mohammed Waleed Kadous
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: waleed@cse.unsw.edu.au |
The availability of high quality open source solutions has often led
to rapid growth of a particular area; most famously, the LAMP
(Linux-Apache-MySQL) platform for Web development that has made it
easy for small entities to set up rich web sites easily. Recent
developments in open source speech recognition software, notably the
Sphinx 4 system, mean that potentially the same could occur for
speech. However, one outstanding issue is the availability of
high-quality acoustic models required for such systems to function
effectively.
This report outlines the possibilities for a new model for speech
corpus repository, based on the principles of Open Source and the
Creative Commons licenses.
Rather than the usual approach for gathering corpora that are done in
a centralised location, using fixed high-quality equipment, we propose
that donors record audio passages using their own equipment and upload
them to a central repository for processing. The data in the speech
repository could be used for training acoustic models for speech
recognition by anyone.
In addition, such a speech repository, especially when combined with
co-located computational processing facilities, such as a Beowulf
cluster, create an opportunity for new applications, for example, the
possibility of personalised acoustic models. Such a system would
customise an acoustic model for a particular user, not just using that
person's data, but by using people whose voices are similar.
Keywords: speech recognition, speech corpus, open source, creative
commons. |
| 0438 |
The Holes Problem in Wireless Sensor Networks: A Survey |
Nadeem Ahmed, Salil S. Kanhere, Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {nahmed, salilk, sjha}@cse.unsw.edu.au |
Several anomalies can occur in wireless sensor networks that impair their desired
functionalities i.e. sensing and communication. Different kinds of holes can form
in such networks creating geographically correlated problem areas such as coverage
holes, routing holes, jamming holes, sink/black holes and worm holes, etc.
We detail in this report different types of holes, discuss their characteristics and
study their effects on successful working of a sensor network. We present state-of-
the-art in research for addressing the holes related problems in wireless sensor
networks and discuss the relative strengths and short-comings of the proposed
solutions for combating different kinds of holes. We conclude by highlighting
future research directions. |
| 0436 |
Secure Online Elections |
Roland Wen
School of Computer Science and Engineering
The University of New South Wales
Sydney, NSW, 2052, Australia
Email: rolandw@cse.unsw.edu.au |
Advances in cryptography have contributed significantly to the Internet
revolution, and one of the next major applications is secure online
elections. In the wake of the debacle of the US presidential election in
2000, governments have rapidly begun to adopt online voting. However,
this is somewhat premature given the current state of research. No
existing election scheme is able to satisfy all the democratic
principles of traditional elections whilst also being suitable for large
scale voting.
This report is intended to be a self-contained introduction to the field
of online elections. It develops the necessary background knowledge,
firstly by examining the traditional and online models, as well as the
requirements and properties for election protocols. Then it presents an
overview of the relevant mathematical and cryptographic preliminaries.
The crux of this report is the survey of the most important election
schemes found in the literature. These are categorised according to the
approach on which they are based: homomorphic encryption, mix nets and
blind signatures. A description and evaluation of each scheme is
provided, followed by a comparison of all the protocols and a discussion
of the limitations and outstanding concerns. |
| 0435 |
A Comparison of Four Software Architecture Reconstructions Toolkits |
Meena Jha, Piyush Maheshwari
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: meenaj@cse.unsw.edu.au |
This report discusses the evaluation of four software architecture reconstruction
tools. This evaluation is needed because many legacy system needs to be
reconstructed as the requirements change for the purpose of modernization.
Software reconstruction is a tool-based iterative and interpretive process.
Software architecture reconstruction tools support software engineers in the
process of recovering the .as-built. architecture of an implemented system.
The tools extract information about the system and aid in building and
aggregating successive levels of abstraction. If the tools are successful, the
end result is an architectural representation aids in reasoning about the system.
There are several commercial reconstruction tools on the market providing
different capabilities and supporting specific source code languages. In this
report, we evaluate four software architecture reconstruction tools on the
criteria of extraction ability, abstraction ability, navigation ability, ease-of-use,
views, completeness and extensibility. The tools presented for evaluation are
Dali workbench, PBS, SWAG Kit and Bauhaus. Capabilities of these tools
are evaluated by applying them to medium size software .concepts.. |
| 0434 |
On Reachability and Acyclicity |
Yi Lu and John Potter
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {ylu,potter}@cse.unsw.edu.au |
This paper presents a type system that enforces constraints on
reachability via pointers or references, and restricts reference
cycles to be within definable regions. Every data object lives in a
fixed region, determined from its type.
The motivation for our work is the desire to enforce static
constraints on reference structures. Such constraints can be useful
for program reasoning, for deadlock avoidance in concurrent
contexts, and for runtime optimizations and memory management. For
example, data invariants are easily broken by re-entrant code. By
restricting cycles to statically enforceable regions, program proof
rules can make stronger assumptions about reference structures.
The contributions of this paper are a novel class-based
region-parametric type system, with subtyping, that enforces one-way
reachability between regions, and a dynamic semantics that allows us
to formalize the key structural invariant: object references respect
region reachability, so that object cycles occur only within
regions. |
| 0433 |
A Quality-Driven Systematic Approach for Architecting Distributed
Software Applications |
Tariq Al-Naeem1, Ian Gorton2, Muhammed Ali Babar12, Fethi Rabhi3 and
Boualem Benatallah1
1 School of Computer Science & Engineering, University of New South Wales,
Austraia; {tariqn,malibaba,boualem@cse.unsw.edu.au}
2 National ICT Australia Ltd; {ian.gorton@nicta.com.au}
3 School of Information Systems, Technology and Management, University of
New South Wales, Australia; {f.rabhi@unsw.edu.au} |
Architecting distributed software applications is a complex design activity.
It involves making decisions about a number of inter-dependent design choices
that relate to a range of design concerns. Each decision requires selecting
among a number of alternatives; each of which impacts differently on various
quality attributes. Additionally, there are usually a number of stakeholders
participating in the decision-making process with different, often conflicting,
quality goals, and project constraints, such as cost and schedule. To facilitate
the architectural design process, we propose a quantitative quality-driven
approach that attempts to find the best possible fit between conflicting
stakeholders' quality goals, competing architectural concerns, and project
constraints. The approach uses optimization techniques to recommend the optimal
candidate architecture. Applicability of the proposed approach is assessed using
a real system. |
| 0432 |
Helping Users Avoid Bugs in GUI Applications |
Amir Michail
University of New South Wales
Sydney, NSW, Australia, 2052
amichail@cse.unsw.edu.au
Tao Xie
University of Washington
Seattle, WA, USA, 98195
taoxie@cs.washington.edu |
In this paper, we propose a method to help users avoid bugs in GUI
applications. In particular, users would use the application normally and
report bugs that they encounter to prevent anyone -- including themselves --
from encountering those bugs again. When a user attempts an action that has
led to problems in the past, he/she will receive a warning and will be given
the opportunity to abort the action thus avoiding the bug altogether and
keeping the application stable. Of course, bugs should be fixed eventually by
the application developers, but our approach allows application users to
collaboratively help each other avoid bugs thus making the application more
usable in the meantime. We demonstrate this approach using our "Stabilizer"
prototype. We also include a preliminary evaluation of the Stabilizer's bug
prediction. |
| 0431 |
An Energy Efficient Select Optimal Neighbor Protocol for Wireless
Ad Hoc Networks |
Bao Hua Liu
University of New South Wales
Sydney, NSW, Australia, 2052
miu@cse.unsw.edu.au
Yang Gao
University of New South Wales
Sydney, NSW, Australia, 2052
yangg@cse.unsw.edu.au
Chun Tung Chou
University of New South Wales
Sydney, NSW, Australia, 2052
ctchou@cse.unsw.edu.au
Sanjay Jha
University of New South Wales
Sydney, NSW, Australia, 2052
sjha@cse.unsw.edu.au |
In this paper, we propose two location-aware select optimal neighbor
(SON) algorithms that are suitable for CSMA/CA based MAC protocols for
wireless ad hoc networks. Both algorithms optimize the energy efficiency
by reducing the effective number of neighbors and thus reduce the
transmission power as well as the overhearing power consumption at
irrelevant receivers. NS-2 simulations show that our algorithms can
achieve about 28\% and 38\% average energy savings per node compared to
CSMA/CA based MAC protocols such as IEEE 802.11. When electronic energy
consumption is a considerable part of energy consumption, SON has a
better energy performance than traditional optimal pruning algorithm. |
| 0429 |
Using Frequency Division to Reduce MAI in DS-CDMA Wireless Sensor Networks |
Bao Hua Liu
University of New South Wales
Sydney, NSW, Australia, 2052
miu@cse.unsw.edu.au
Chun Tung Chou
University of New South Wales
Sydney, NSW, Australia, 2052
ctchou@cse.unsw.edu.au
Justin Lipman,
University of New South Wales
Sydney, NSW, Australia, 2052
justinl@cse.unsw.edu.au
Sanjay Jha
University of New South Wales
Sydney, NSW, Australia, 2052
sjha@cse.unsw.edu.au |
The performance of Direct Sequence Code Division Multiple Access (DS-CDMA) sensor networks is limited by Multiple Access Interference (MAI). This paper proposes using frequency division to reduce the MAI in a DS-CDMA sensor network. We provide theoretical characterization of the mean MAI at a given node and show that a small number of frequency channels can reduce the MAI significantly. In addition, we provide a comparison of our proposed system to systems which do not use frequency division or which employ contention based protocols. Our study found that, by using only a small number of frequency channels, our system has less channel contention, lower packet latency, higher packet delivery ratio and lower energy consumption. |
| 0428 |
Policy-Based Exception Handling in Business Processes |
Rachid Hamadi and Boualem Benatallah
School of Computer Science and Engineering
The University of New South Wales
Sydney, NSW 2052, Australia
{rhamadi,boualem}@cse.unsw.edu.au |
A workflow management system (WfMS) provides a central control point
for defining business processes and orchestrating their execution.
A major limitation of current WfMSs is their lack of support for
dynamic workflow adaptations.
This functionality is an important requirement in order to provide
sufficient flexibility to cope with expected but unusual situations
and failures.
In this report, we propose Self-Adaptive Recovery Net (SARN), an
extended Petri net model for specifying exceptional behavior in
workflow systems at design time.
SARN can adapt the structure of the underlying Petri net at run
time to handle exceptions while keeping the Petri net design simple
and easy.
The proposed framework also caters for high-level recovery policies
that are incorporated either with a single task or a set of tasks,
called a recovery region.
These recovery policies are generic constructs that model exceptions
at design time together with a set of primitive operations that can
be used at run time to handle the occurrence of exceptions. |
| 0424 |
Querying and Maintaining Succinct XML Data |
Franky Lam, William M. Shui, Damien K. Fisher, Raymond K. Wong
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia |
As XML database sizes grow, the amount of space used for storing the data and
auxiliary supporting data structures becomes a major factor in query and update
performance. This paper presents a new secondary storage scheme for XML data
that supports all navigational operations and answers ancestor queries in near
constant time. In addition to supporting fast queries, the space requirement
is within a constant factor of the information theoretic minimum, while
insertions and deletions can be performed in near constant time as well. As a
result, the proposed structure features a small memory footprint that increases
cache locality, whilst still supporting standard APIs such as DOM efficiently.
As an example of the scheme's power, we further demonstrate that the structure
can support efficient structural and twig joins. Both formal analysis and
experimental evidence demonstrate that the proposed structure is space and time
efficient. |
| 0423 |
Incremental Schema Validation for XML Databases |
Damien K. Fisher, Raymond K. Wong
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia |
An important feature of any database system is the ability to perform
consistency checks on the data being manipulated in the system. For XML
databases, the most fundamental such check is validation with respect to a
fixed data schema, such as a DTD or XML Schema. While it is straightforward to
perform such validation on an entire XML document, it would be extremely
inefficient to revalidate the entire database from scratch upon every
modification. Hence, it is natural to ask whether efficient incremental schema
validation techniques exist.
In this report, we investigate the complexity bounds of such techniques for a
variety of schema languages. As with previous work on this subject, we mainly
study the related problem of dynamic membership in a regular language. We
define a class of regular expressions for which dynamic membership can be
determined in constant time, and a larger class for which dynamic membership
can be determined in O(log log n) time. We also show that, in general,
validation can be performed in time O(log n / log log n), and that this
bound is tight for some schemas. |
| 0421 |
Emphysema Detection Using a Density Mask |
Mario Bou-Haidar, Mithun Prasad, Arcot Sowmya
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: mariob@cse.unsw.edu.au |
This report describes an accurate approach to emphysema detection
using HRCT (high resolution computer tomography) lung images. It is
based on a suite of image processing techniques on top of "Density
Mask". "Density Mask" is a standard approach currently used for
emphysema detection in medical image analysis. The motivation behind
this work lies in the fact that "Density Mask" results in noisy
regions of Emphysema. As a result, a heuristic based method that
filters out unwanted noise from the HRCT images is useful. The
experiments were based on finding the right heuristic parameters for
successful detection of Emphysema regions. Radiologists in the team
have verified the results and concluded that the approach is capable
of detecting very sensitive emphysema. |
| 0420 |
Profile-Guided Partial Redundancy Elimination
Using Control Speculation: a Lifetime Optimal Algorithm
and an Experimental Evaluation |
Jingling Xue and Qiong Cai
Programming Languages and Compilers Group
School of Computer Science and Engineering
University of New South Wales
Sydney, NSW 2052, Australia}
{jxue,qiongc}cse.unsw.edu.au |
A lifetime optimal algorithm, called MCPRE, is presented for the
first time that performs partial redundancy elimination (PRE) by
combining code motion and control speculation based on an edge
profile. An edge profile provides an approximation of the actual edge
frequencies with the predicted edge frequencies. MCPRE is developed
so that the optimality results it achieves are reasoned about with respect
to a given edge profile. MCPRE is computationally optimal since
the total number of dynamic computations for an expression in the
transformed code is minimized. If the predicted frequencies of all
flow edges are nonzero, MCPRE is also lifetime optimal since the
lifetimes of introduced temporaries in the transformed code are also
minimized. Otherwise (if some flow edges are zero-weighted), MCPRE
yields a practical transformation (as validated by extensive experiments)
from the perspective that the predicted zero frequencies are (or should be)
interpreted as the least frequently rather than never executed at all.
The computational and lifetime optimality results are rigorously proved.
This algorithm works on CFGs with standard basic blocks and is conceptually
simple. First, it performs two standard bit-vector data-flow analyses,
availability and partial anticipability, to transform a given CFG to an
s-t flow network. It then relies on a min-cut solver to find a unique
minimum cut on the flow network. Finally, it performs a third standard
live range analysis to avoid making unnecessary code insertions and replacements
for isolated computations. We have implemented the MCPRE algorithm in gcc 3.4
and evaluated its performance against Knoop, R{\"u}thing and Steffen's
profile-independent LCM, the built-in PRE pass at gcc's O2 optimization level
and above. We report and analyze our experimental results for all 22
C, C++ and FORTRAN 77 benchmarks from SPECcpu2000 on two computer architectures,
Intel Xeon and UltraSPARC-III. Our results show that MCPRE is both effective
(in terms of the extra redundancies eliminated and performance improvements
achieved) and practical (in terms of the relatively small compilation and
space overheads introduced). |
| 0419 |
Mapping basic recursive structures to runtime reconfigurable hardware |
Hossam ElGindy And George Ferizis
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {hossam,gferizis}@cse.unsw.edu.au |
Recursion is a powerful method that is used to describe many algorithms
in computer science.
Processing of recursion is traditionally done using a stack, which can act as a
bottleneck for parallelising and pipelining different stages of recursion. In this
paper we propose a method for mapping recursive algorithms, without the use of a
stack structure, into hardware by pipelining the stages of recursion.
The use of runtime reconfigurable hardware to minimise the amount of required
hardware resources, and the related issues to be resolved, are addressed. |
| 0418 |
Incremental Learning of Linear Model Trees |
Duncan Potts and Claude Sammut
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: duncanp@cse.unsw.edu.au and claude@cse.unsw.edu.au |
A linear model tree is a decision tree with a linear functional model
in each leaf. Previous model tree induction algorithms have operated
on the entire training set, however there are many situations when an
incremental learner is advantageous. In this report we demonstrate that
model trees can be induced incrementally using an algorithm that scales
linearly with the number of examples. Two incremental node splitting
rules are presented, together with incremental methods for stopping
the growth of the tree and pruning. Empirical testing in four domains
ranging from a simple test function to a complex 13 dimensional flight
simulator, shows that the new algorithm can learn a more accurate
approximation from fewer examples than alternative incremental methods.
In addition a batch implementation of the new algorithm compares
favourably with existing batch techniques at constructing model trees
in these domains. Moreover the induced models are smaller, and the
learners require less prior knowledge. |
| 0415 |
Requirements Engineering for e-Business Advantage |
Steven J. Bleistein, Karl Cox, and June Verner
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: stevenb@cse.unsw.edu.au |
As a means of contributing to the achievement of business advantage
for companies engaging in e-business, we propose a requirements
engineering approach that incorporates a business strategy
dimension. We employ both goal modeling and Jackson's Problem Frames
approach to achieve this. Jackson's context diagrams, used to
represent the business model context, are integrated with goal-models
to describe the complete business strategy. We leverage the paradigm
of projection in both approaches while maintaining traceability to
high-level business objectives as a means of simultaneously
decomposing both the optative and indicative parts of the requirements
problem, from an abstract business level to concrete system
requirements. We integrate use of role activity diagrams to describe
business processes in detail where needed. The feasibility of our
approach is shown by a case study. |
| 0414 |
A Use Case Description Inspection Experiment |
Karl Cox, Aybüke Aurum, Ross Jeffery
School of Computer Science and Engineering
University of New South Wales
Sydney 2052
Australia
Email: karlc@cse.unsw.edu.au |
Achieving higher quality software is one of the aims sought
by development organizations worldwide. Establishing defect free
statements of requirements is a necessary prerequisite to this goal.
In this paper we present the results of a laboratory experiment that
explored the application of a checklist in the process of inspecting
use case descriptions. A simple experimental design was adopted in
which the control group used an ad hoc approach and the treatment
group was provided with a six-point checklist. The defects identified
in the experiment were classified at three levels of significance:
i. Internal to the use case ii. Specification impact, and
iii. Requirements impact. It was found that the identification of
requirements defects was not significantly different between the
control and treatment groups, but that more specification and internal
defects were found by the groups using the checklist. In the paper we
explore the implications of these findings. |
| 0413 |
Support Vector Machine Experiments for Road Recognition in High Resolution Images |
James Lai
School of Computer Science and Engineering
The University of NSW, Australia
jlai@cse.unsw.edu.au
Arcot Sowmya
School of Computer Science and Engineering
The University of NSW, Australia
sowmya@cse.unsw.edu.au
John Trinder
School of Surveying and Spatial Information Systems
The University of NSW, Australia
j.trinder@unsw.edu.au |
Support Vector Machines have received considerable attention from the pattern recognition community in recent years. They have been applied to various classical recognition problems achieving comparable or even superior results to other classifiers such as neural networks. We investigate the application of Support Vector Machines (SVMs) to the problem of road recognition from remotely sensed images using edge-based features. We present very encouraging results in our experiments, which are comparable to decision tree and neural network classifiers. |
| 0412 |
Maintaining End-system Performance under Network Overload |
Luke Macpherson, Gernot Heiser
School of Computer Science and Engineering
and National ICT Australia
University of New South Wales
Sydney 2052, Australia
E-mail: {lukem, gernot}@cse.unsw.edu.au |
Network performance is currently outpacing the performance
improvements seen by host systems, leading to a significant performance
gap between the throughput which may be supported by a network
interface, and the actual throughput which can be achieved by a typical
end-system. Because this is the case, end-systems must be able to cope
with applied loads which exceed their capacities. In particular, system
performance in terms of latency, throughput, and jitter should not
deteriorate under overload.
This paper evaluates the use of intelligent software-based
control algorithms adjusting the interrupt-holdoff time and the
available DMA buffer space in order to prevent
receive livelock on commodity hosts and network adaptors. We present a
simple analytical model of packet latency, which allows us to analyse
system performance under overload.
The control algorithm has been implemented in the FreeBSD
operating system. Experiments show excellent scalability under overload,
comparing favourably with previous approaches. Furthermore, the
implementation is less intrusive on operating system design than prior
approaches with similar goals. |
| 0411 |
Parallelized FTP:- Effective approach for Solving
Huge Download Delay Problem over Internet |
Shaleeza Sohail and Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {sohails,sjha}@cse.unsw.edu.au |
The file download process over Internet is usually slow and
unpredictable. We have designed and implemented a distributed
and co-ordinated file transfer protocol for the Internet
applications. We have designed and implemented a centralized
server that distributes the download process across multiple
file servers based on such QoS parameters as available bandwidth
and delay. In addition to this, we monitor the FTP flows to
detect slow servers and congested links and adjust the file
distributions accordingly. Early experimentation suggests that
our method can reduce the download time by more than 50% for
large files. In addition to reducing the delay our technique
has an added advantage that it does not need any modifications
to the existing FTP implementations. |
| 0410 |
Requirements Engineering for Business Advantage: the Strategy Dimension of e-Business Systems |
Steven J. Bleistein, Karl Cox, and June Verner
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: stevenb@cse.unsw.edu.au |
As a means of contributing to achievement of business advantage for
companies engaging in e-business we propose a requirements engineering
approach for e-business systems that incorporates a business strategy
dimension. We employ both goal modeling and Jackson's Problem Frames
approach to achieve this. Jackson's context diagrams, which are used
to represent the business model context, are integrated with
goal-models to describe the complete business strategy. As a means of
simultaneously decomposing both the optative and indicative parts of
the requirements problem, from an abstract business level to concrete
system requirements, we leverage the paradigm of projection in both
approaches while maintaining traceability to high-level business
objectives. A proof-of-concept case study from the literature shows
the feasibility of our approach. |
| 0409 |
Dynamic Path Restoration Algorithms For On-Demand Survivable Network Connections |
William Lau and Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {wlau,sjha}@cse.unsw.edu.au |
Restoration strategies that use offline pre-planning assume that the
traffic matrix is static and is known prior to the network capacity
assignment. These strategies require recalculation of the capacity
requirement for any changes made to the traffic matrix, thus are not
suitable for use in highly dynamic traffic environments.
This paper addresses the dynamic online capacity assignment problem
where each source-destination restoration request is computed
sequentially with no prior knowledge of requests that have not been
calculated. We focus on the state-dependent approach that allows
different backup paths to be used when the network suffers different
failure scenarios.
The problem is first formulated into a new Integer Programming (IP)
problem, and new heuristics are proposed that make trade-offs between
bandwidth efficiency and computation time. Results show that the
proposed polynomial-time algorithm performs competitively with the IP
solution in terms of bandwidth efficiency, and performs better than
existing heuristic algorithms of the same restoration strategy. The
computation time for the polynomial-time algorithm is significantly
shorter than the IP solution and thus suitable for large scale
on-demand applications.
Further, a comprehensive performance comparison is made between online
algorithms of state-dependent and state-independent strategies.
Results from this analysis can be used as a guide for choosing between
the two strategies. State-dependent algorithms are shown to provide
better trade-offs between network efficiency and computation-time, as
compared with state-independent algorithms. |
| 0408 |
Multicast Resilience with Quality of Service Guarantees |
William Lau and Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {wlau,sjha}@cse.unsw.edu.au
Suman Banerjee
Department of Computer Sciences
University of Wisconsin-Madison
Madison, WI 53706, USA
suman@cs.wisc.edu |
This paper defines new algorithms for providing bandwidth guaranteed
multicast support to applications that require resilience in presence
of link failures in the network. Our techniques are applicable for
networks that are capable of native network-layer multicast as well as
networks that have been enhanced to support infrastructure-based
overlay multicast. For efficient multicast restoration, which are
necessary for such a construction, we based our techniques on online
computation and dynamic routing. We define new Integer Linear
Programming (ILP) solutions to the problem, and from experience with
the ILP solutions, we derive heuristics that are used to form a new
polynomial-time algorithm.
Results from our experiments show that our proposed mechanisms can
significantly improve the bandwidth efficiency (by 55%) and request
acceptance rate (by a factor of 1.5) over alternative mechanisms. The
benefits are comparable for infrastructure-based overlay multicast
scenarios. Our results also indicate that the proposed heuristics
solution performs within 12% of the ILP formulation solution with
respect to different metrics. |
| 0406 |
NightOwl: Self-Localisation by Matching Edges |
Raymond Sheh
Department of Computing
Curtin University of Technology
Perth 6102 Australia
and
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: shehrk@cs.curtin.edu.au
Bernhard Hengst
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
and
National ICT Australia
University of New South Wales
Sydney 2052 Australia
E-mail: bernhardh@cse.unsw.edu.au |
A mobile robot must know where it is to act appropriately. An algo-
rithm that allows a robot to accurately localise itself locally using a vision
sensor and a map of its environment is described in this paper. The basic
idea of this algorithm, called NightOwl, is to match the projected camera
image with a map of the environment in a local area in order to find the
most likely position and orientation of the camera platform. |
| 0405 |
Present Issues & Challenges in Survivable WDM Optical Mesh Networks |
Amitava Mukherjee
School of Computer Science & Engineering
University of New South Wales, Sydney 2052, Australia
E-mail: amitavam@cse.unsw.edu.au
Asidhara Lahiri
IBM Global Services
Salt Lake, Calcutta 700 091, India
E-mail:asidhara.lahiri@in.ibm.com
Debashis Saha
MIS & Computer Science Group, Indian Institute of Management (IIM) Calcutta,
Joka, Kolkata 700 104, India
E-mail: ds@iimcal.ac.in |
The design of survivable optical networks is obtained by exploiting
restoration and/or protection schemes in the WDM and IP layers. In
this paper, we discuss the different restoration and protection
techniques available at the IP and WDM layers. Upon network failure, a
restoration scheme dynamically looks for backup paths of spare
capacity in the network. A protection scheme reserves, in advance,
dedicated backup paths and wavelengths in the network. The former
scheme is commonly available at higher layers (e.g., the IP
layer). The latter scheme is commonly used at the transport (e.g.,
WDM) layer. The WDM predefined protection scheme is broadly divided
into link-based and path-based protection. Predesigned protection
schemes are so far the most studied for WDM networks. Because of the
multichannel traffic, the design algorithms used in a WDM network are
more complex than those used in non-WDM systems. The survivability
schemes available at the network layer, such as IP (IP/MPLS), have the
capability to recover multiple faults and operate at small traffic
granularity. A primary concern for this approach is the slow
convergence and response time of IP link failure detection and routing
algorithms that renders them unsuitable for use with critical or
premium services. This paper discusses the recent works on the
restoration and/or protection schemes in the WDM and IP layers and few
future research issues. |
| 0404 |
Approaches for Radio Resource Management in Mobile Wireless Networks: Current Status and Future Issues |
Amitava Mukherjee
School of Computer Science & Engineering
University of New South Wales, Sydney 2052, Australia
E-mail: amitavam@cse.unsw.edu.au
Debashis Saha
MIS & Computer Science Group, Indian Institute of Management (IIM) Calcutta, Joka, Kolkata 700 104, India
E-mail: ds@iimcal.ac.in |
The rapid growth of wireless mobile community, coupled with their
demands for high speed, wide band, multimedia services, stands in
clear contrast to the limited radio spectrum allocated in
international agreements. So radio resource management (RRM) remains
as a key challenge to the efficient engineering of mobile wireless
networks. In this report, we present an overview of the current status
of RRM polices and outline the key issues in RRM for next generation
mobile wireless networks. |
| 0403 |
Design Recovery of Real-Time Graphical Applications using Video |
Kim Cuong Pham, Tran Quan Pham, Amir Michail
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {kcph007,quanpt,amichail}@cse.unsw.edu.au |
In a previous paper, we introduced an approach to design recovery
that takes advantage of the interactive and graphical nature of the
majority of today's applications. This earlier work is applicable
only to interactive graphical applications written in an event-driven
programming style with alternation between user-initiated events and
application responses. While productivity applications such as word
processors and spreadsheets are of this form, real-time graphical
applications such as flight simulators and games are not, since the
application proceeds even while the user is idle. In this paper, we
propose a design recovery method for real-time graphical applications
that uses video to link lower-level code events with their
higher-level graphical manifestations. We demonstrate by example how
the more easily understood video can shed light on the harder to
understand implementation of a real-time graphical application. |
| 0402 |
Case Study to Monitor Cane Toads in Kakadu National Park |
Saurabh Shukla, Nirupama Bulusu, Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: sshu495@cse.unsw.edu.au, nbulubu@cse.unsw.edu.au,
sjha@cse.unsw.edu.au |
Recent advances in wireless communication have promoted the large-scale research
in development and deployment of sensor networks. Networked sensors that
coordinate among themselves to perform large tasks are expected to revolutionize
information gathering and processing in near future.
This thesis addresses the problem of large scale sensor deployment using the
application of monitoring cane toads in Kakadu National Park as a case study.
cane toads were introduced in Australia by mistake in 1935. Their uncanny
ability to survive in diverse climates and lack of natural predators in the
Australian ecosystem have promoted unhindered growth of cane toads for the last
68 years This application is of tremendous importance to Australia because cane
toads are endangering native species and the ecosystem.
A study of deployment requirements is important because it influences the network
and system architecture; and consequently the design considerations for
higher layer protocols and algorithms.
Previously proposed deployment work (especially in the sensor networks context)
tries to achieve a single objective (e.g maximizing sensor coverage in a given
area; or maintaining radio connectivity.) Deployment has not really been
studied in terms of a higher-level application perspective when many
objectives have to be satisfied simultaneously.
This work bridges that gap. Our thesis is that deployment is really a
multi-variate problem and we provide a novel framework to studying deployment
by integrating application, economic, and networking/technology objectives.
Specifically, the contributions of the thesis are:
a) A framework in which the deployment problem can be reduced to:
Zone division: Division of deployment area into zones.
Zone classification: Classification of zones based on deployment priorities.
In-zone deployment: Strategies for deploying nodes within a zone to meet the bandwidth
and coverage requirements.
b) Observation that it is hard to get initial deployment right due to
uncertainty. Bayesian framework is used for addressing uncertainty in domain
knowledge and using it to drive adaptive learning algorithm
c) Discussion of evaluation strategies
Working through a deployment strategy for cane toad monitoring reflects a
hierarchical hybrid network of possibly many mutually disconnected clusters;
which is counter-intuitive to the large-scale "flat" network models commonly
assumed. Although our study is in the context of a single specific
application, we hope the insights from our study will be useful to designers
and researchers in the area of sensor networks.
The final aim is to assist the ecologist and biologist in their pursuit of
limiting the growth of toads in the region. The goal is to develop a deployment
strategy for sensor networks in Kakadu National Park. The sensor network thus
designed will be used to monitor and track the presence of cane toads in the
Kakadu National Park. |
| 0401 |
A CDMA-Based, Self-Organizing, Location-Aware Media Access Control Protocol |
Bao Hua (Michael) Liu
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: mliu@cse.unsw.edu.au
Nirupama Bulusu
National ICT Australia Ltd.
E-mail: nbulusu@cse.unsw.edu.au
Huan Pham
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: huanp@cse.unsw.edu.au
Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: sjha@cse.unsw.edu.au |
In this paper, we propose CSMAC, a novel CDMA-based, self-organizing,
location-aware media access control (MAC) protocol for sensor
networks. We argue that no single MAC protocol is suitable for all
sensor network applications, which cover a broad range of application
domains from wildlife tracking to real-time battlefield
surveillance. Previously proposed MAC protocols for sensor networks
such as S-MAC primarily prioritize energy-efficiency over latency. Our
protocol design balances the considerations of energy-efficiency,
latency, accuracy, and fault-tolerance in sensor networks. CSMAC uses
Code Division Multiple Access to reduce channel interference and
consequently message latency in the network. It exploits location
awareness to improve energy-efficiency by employing two special
algorithms in the network formation process --- Turn Off Redundant
Node (TORN) and Select Minimum Neighbor (SMN). ns-2 simulations show
that in a 10-hop network topology, CSMAC can achieve upto 74% lower
mean latency than SMAC, while consuming 41% lower mean energy per
node. |
| 0337 |
Present Scenarios and Future Challenges in Pervasive Middleware |
Amitava Mukherjee
School of Computer Science & Engineering
University of New South Wales, Sydney 2052, Australia
E-mail: amitavam@cse.unsw.edu.au
Debashis Saha
MIS & Computer Science Group, Indian Institute of Management (IIM) Calcutta, Joka, Kolkata 700 104, India
E-mail: ds@iimcal.ac.in |
In order to run applications on pervasive devices, pervasive
middleware has to support context-awareness, as pervasive applications
need to adapt to variations of context of execution (such as network
bandwidth, battery power and screen size), physical change of
locations, change of technological artifacts (devices), change of
hardware resources of artifacts, and so on. Recent research efforts
have primarily focused on designing new mobile middleware systems
capable of supporting the requirements imposed by mobility. However,
apart from mobility constraint, pervasive middleware will operate
under above-mentioned conditions of a radical change. This change is
varying from physical components (like network heterogeneity) to
functional components (right from heterogeneous devices to
context-based applications). Few contemporary researches have indeed
focused on some parts of these requirements; but a qualitative
difference between intended requirements and practical achievements
still remains there. In this article, we discuss some of recent
mobile/pervasive middleware systems, focusing on research issues and
challenges ahead to bridge the gap. Typically, we highlight the key
characteristics of pervasive middleware to support context awareness
and service discovery, smartness and adaptation, heterogeneity and
integration, and intelligent interfacing. |
| 0336 |
Exploring the Issues of Boundary Definition in the Application of COSMIC-FFP
to Embedded Systems |
Jacky Keung, Suryaningsih, Ross Jeffery
National ICT Australia &
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {jkeung, rossj}@cse.unsw.edu.au |
Software sizing plays an essential role in software management and in providing input for
estimation and benchmarking purposes. Despite the claim of emerging popularity of function
points as a size measure, it is not widely accepted in all software domains.
The most popular technique is Function Point Analysis that has become the “de-facto” standard
in the business application environment. When applied to non-MIS systems many researchers
have criticized the counts as misleading and not reflective of the size of the systems.
The release of COSMIC Full Function Point technique is aimed at overcoming these shortcomings.
This paper presents a single-case study in a telecommunication company to examine the
applicability of the COSMIC Full Function Point technique in the domain of embedded telephone
switching systems (a type of real-time system). Through the experience of this study,
it is found that there is very limited experience in this area.
The current counting convention is thought to be inadequate in many areas such as peer-to-peer
sizing and that the field is still evolving. Due to uncertainty and ambiguity in the measurement
process, counter’s subjectivity plays an important role in function point counting. |
| 0335 |
Planning an Empirical Experiment To Evaluate The Effects Of Pair Work On The Design Phase Of The Software Lifecycle |
H. Al-Kilidar, R. Jeffery, C. Kutay
School of Computer Science and Engineering
University of New South Wales, NSW 2052,
Australia
E-mail: {hiyama| rossj| ckutay}@cse.unsw.edu.au
A. Aurum
School of Information Systems, Technology and Management
University of New South Wales, NSW 2052,
Australia.
E-mail: aybuke@unsw.edu.au |
This report presents the details of an empirical experiment designed
to evaluate the effects of Pair Work on the design phase of software
development lifecycle. The experiment is designed to investigate the
effects of pair work on the quality of design products and whether the
pair work approach in the design process is more efficient or cost
effective than individual work approach. The aims of the experiment
are to compare the quality of the design products produced by pair
designers and individual designers as well as compare the efficiency
and cost effectiveness of the pair work approach and the individual
work approaches in the design process. In addition, the experiment
studies the partner's expectations and practices during the pair work
experience. The experimental hypotheses, design, inputs, outputs, and
evaluation measures will be described. |
| 0331 |
An Anycast Service for Hybrid Sensor/Actuator Networks |
Wen Hu
School of Computer Science and Engineering
The University of NSW, Australia
wenh@cse.unsw.edu.au
Nirupama Bulusu
National ICT Australia Limited
nbulusu@cse.unsw.edu.au
Sanjay Jha
School of Computer Science and Engineering
The University of NSW, Australia
sjha@cse.unsw.edu.au
Patrick Senac
ENSICA-LAAS/CNRS
senac@ensica.fr |
This paper investigates an anycast communication service for a hybrid sensor/actuator
network, consisting of both resource-rich and resource-impoverished devices. The key idea
is to exploit the capabilities of resource-rich devices (called micro-servers) to reduce the
communication burden on smaller, energy, bandwidth and memory constrained sensor nodes.
The goal is to deliver sensor data to the nearest micro-server, which can (i) store it (ii) forward
it to other micro-servers using out-of-band communication or (iii) perform the desired actuation.
We motivate, propose, evaluate and analyse a reverse tree-based anycast
mechanism tailored to deal with the unique event dynamics in sensor networks.
Our approach is to construct an anycast tree rooted at each potential event
source, which micro-servers can dynamically join and leave.
Our anycast mechanism is self-organizing, distributed, robust, scalable, routing-protocol
independent and incurs very little overhead. Simulations using ns-2 show that our anycast mechanism when
added to Directed Diffusion can reduce the network's energy consumption by more than 50%, can
reduce both the mean end-to-end latency of the transmission and the mean
number of transmissions by more than 50%, and achieves 99% data delivery rate
for low and moderate micro-server mobility rate. |
| 0328 |
State Transition Model to Characterize TCP Window Control Behavior in Wired/Wireless Internetworks |
Debashis Saha
MIS & Computer Science Group, Indian Institute of Management (IIM) Calcutta, Joka, Kolkata 700 104, India
E-mail: ds@iimcal.ac.
Amitava Mukherjee
School of Computer Science & Engineering
University of New South Wales, Sydney 2052, Australia
E-mail: amitavam@cse.unsw.edu.au
Sanjay K Jha
School of Computer Science & Engineering,
University of New South Wales, Sydney 2052, Australia
E-mail: sjha@cse.unsw.edu.au |
TCP was designed to work well in networks with low channel error rates.
Wireless networks on the other hand are characterized by frequent
transmission losses. As a result, when TCP is used in wired/wireless
internetworks, the losses due to channel errors are mistaken as congestion
losses and the sending rate is unnecessarily reduced in an attempt to
relieve the congestion, resulting in a degraded performance. There are
several studies to model the behavior of TCP in such environments,
typically under last-hop wireless scenarios. The consensus is that TCP
needs some form of intimations to segregate wireless loss from
congestion loss and behave accordingly in its window control.
However, it is not an easy task to detect the type of loss from
TCP behavior as shown in this report with the help state transition
models. In order to further extend the model for more accuracy in
capturing the exact TCP window control, we plan to carry out a
series of simulation studies for a synthetic heterogeneous
environment with multiple TCP/UDP flows, keeping the state
diagram in mind. |
| 0325 |
Automated Interface Synthesis |
Vijay D'Silva, Arcot Sowmya
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: vijayd, sowmya@cse.unsw.edu.au
S. Ramesh
Visiting Professor
NICTA Sydney Node
(May-August 2003)
(permanent)
Department of Computer Science and Engineering
Indian Institute of Technology, Powai
Bombay 400 076
E-mail: ramesh@cse.iitb.ac.in |
System-on-Chip (SoC) design methodologies rely heavily on reuse of
intellectual property (IP) blocks. IP reuse is a labour intensive and
time consuming process as IP blocks often have different communication
interfaces. We present a framework which automates the generation of HDL
descriptions of interfaces between mismatched IP communication
protocols. We significantly improve and extend existing work by
formalising the problem and providing a solution which addresses data
mismatches, pipelining and differences in clock speeds. Importantly,
the use of a formal framework enables us to generate solutions which are
provably correct. The developed algorithms have been implemented and the tool
used to synthesise wrappers and bridges for many SoC protocols.
In particular we present a case study of the application of our algorithm
to a specific design obtained from industry. |
| 0323 |
Failure-Oriented Path Restoration Algorithm for Survivable Networks |
William Lau and Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {wlau,sjha}@cse.unsw.edu.au |
Connection-oriented networks such as MPLS and GMPLS offer network
providers the mechanisms to deliver a high level of service quality to
their clients. One critical factor in determining the service quality
is the rate of availability or what some call the up-time of the
connection. A common approach for provisioning high availability with
shorter restoration times is to use pre-calculated backup paths that
are used when the normal service paths fail. The challenge in this
approach is to allocate the minimal total spare capacity required by
the backup paths. One restoration strategy that aims to minimize
spare capacity is based on failure-oriented reconfiguration (FORC),
where a backup path is calculated for each possible scenario that
affects the working service path. Linear and integer programming
formulations can be made to find optimal solutions but do not run in
polynomial time. An existing heuristic algorithm was proposed to
reduce the computation time but it also does not run in polynomial
time.
In this paper, a new polynomial-time approximation algorithm called
Service Path Local Optimization (SPLO) is proposed. SPLO is shown to
perform better than the existing approximations for FORC. SPLO is
designed for online computation where only one request is computed at
any one time, and the decision making does not depend on future
requests. The polynomial-time and online nature of the algorithm make
SPLO suitable for use in real-time on-demand path request
applications. Further, the potential for SPLO as an algorithm in
traffic engineering applications is investigated by looking at the
performance impact when source-destination-based traffic aggregation
is applied. The results show that spare capacity requirement for SPLO
is degraded by up to 5% only.
This paper also introduces a new concept called path intermix where
the service path's allocated bandwidth can be used by the backup paths
protecting that particular service path. The result shows that
path-intermix reduces the lengths of backup paths and can reduce spare
capacity by up to 4% for single node failures. |
| 0322 |
A Theory of Proximity Relations |
Jane Brennan, Eric Martin
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: jbrennan|emartin@cse.unsw.edu.au |
Next to orientation and connectivity, proximity is one of the key topological
properties of many spatial relations.
The aim of the work presented in this report is to provide a formalism
that can qualitatively account for absolute binary proximity relations,
taking into consideration common-sense spatial knowledge.
The theory of nearness presented here is based on the concepts
of influence areas of spatial objects and distances between these objects
abstracted into a pseudo-metric space.
This theory goes beyond existing
models and influence area approaches, by generalising them and providing a
formalisation of nearness notions. The most general nearness notions
are justified against a set of experimental results obtained from studies
conducted by Worboys \cite{worboys2001} in the domain of environmental spaces.
The symmetric notion of nearness, which we found to be an adequate
representation for most cases, is elaborated on in more detail.
Its implications are investigated in the context of a navigational
model.
There are however cases where nearness is not symmetric. Therefore a
brief discussion on the asymmetric aspect of nearness is given
and its implications are investigated in the context of a natural
language model. |
| 0321 |
A Survey on the Interaction Between Caching, Translation and Protection |
Adam Wiggins
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: awiggins@cse.unsw.edu.au |
Fine-grained hardware protection could deliver significant benefits to
software, enabling the implementation of strongly encapsulated
light-weight objects, but only if it can be done without slowing down
the processor.
In this survey we explore the interaction between the processor's
caches and virtual memory in traditional as well as research
architectures. We find that while caching and translation mechanisms
have received much attention in the literature, hardware protection
mechanisms have remained largely neglected, with none of the explored
architectures providing truly scalable support for context-sensitive,
fine-grained protection.
Based on the insights gained from the survey we outline an approach
which facilitates the construction of simple, yet fast, low-power
fine-grained protection mechanisms for processor cores. |
| 0320 |
Skipping Strategies for Efficient Structural Joins |
Franky Lam, William M. Shui, Damien K. Fisher, Raymond K. Wong
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: wong@cse.unsw.edu.au |
The structural join is considered a core operation in processing
and optimizing XML queries. Various techniques have been proposed
for efficiently finding structural relationships between a list of
potential ancestors and a list of potential descendants.
This paper presents a novel algorithm for efficiently processing
structural joins. Moreover, previous work which performs well usually
relies on external index structures such as a B-tree, which increases
both the storage and memory overheads. Our proposal in this paper
does not require any such data structures, and hence can be easily
implemented and incorporated in any existing system. Experiments
show that our method significantly outperforms previous algorithms. |
| 0319 |
Peering and Querying e-Catalog Communities |
Boualem Benatallah (1), Mohand-Said Hacid (2), Hye-young Paik (1)
Christophe Rey (3) and Farouk Toumani (3)
(1) CSE, University of New South Wales, Australia,
{boualem,hpaik}@cse.unsw.edu.au
(2) LIRIS, University Lyon I, France,
mshacid@liris.univ-lyon1.fr
(3) LIMOS, ISIMA, University Blaise Pascal, France,
{rey,ftoumani}@isima.fr |
An increasing number of organisations are jumping hastily
onto the online retailing bandwagon and moving their operations to the
Web. A huge quantity of e-catalogs (i.e., information and product portals)
is now readily available.
Unfortunately, given that e-catalogs are often autonomous and heterogeneous,
effectively integrating and querying them is a delicate and time-consuming task.
More importantly, the number of e-catalogs to be integrated and queried
may be large and continuously changing. Consequently, conventional approaches
where the development of an integrated e-catalog requires the understanding of
each of the underlying catalog are inappropriate.
Instead, a divide-and-conquer approach should be adopted, whereby e-catalogs
providing similar customer needs are grouped together, and semantic peer
relationships among these groups are defined to facilitate distributed,
dynamic and scalable integration of e-catalogs.
In this paper, we use the concept of e-catalog communities and peer
relationships among them to facilitate the querying of a potentially large
number of dynamic e-catalogs. e-Catalogs communities are essentially
containers of related e-catalogs. We propose a flexible query matching
algorithm that exploits both community descriptions and peer relationships
to find e-catalogs that best match a user query. The user query is formulated
using a description of a given community. |
| 0318 |
Intertac Software Architecture |
Cat Kutay
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: ckutay@cse.unsw.edu.au |
This paper describes the development of a groupware system from the
requirements developed through researching the activities of software
engineering students who were developing specification reports in
groups. The specification is designed for an imaginary, but realistic,
client. The groupware was developed to enable these groups to meet
more often in non-collocated sessions. A list of requirements that
were developed for the basic application software are presented here,
together with the Architecture and Interface.
The groupware is designed as a Constructivist and Collaborative
Learning Environment (CLE) so the first aim is to provide a flexible
and unstructured learning environment in which students can construct
their own meaning. On top of this can be placed agents to provide
assistance and feedback to improve aspects of this learning. This
paper looks at the first part of this process, developing the
environment with a component-based architecture to which agents can
readily be integrated. Also brief summary of the agent support is
provided, with a plan for future verification of the final system when
complete. |
| 0317 |
Fast Ordering for Changing XML Data |
Damien K. Fisher, Franky Lam, William M. Shui, Raymond K. Wong
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: wong@cse.unsw.edu.au |
With the increasing popularity of XML, there arises
the need for managing and querying information in this
form. Several query languages, such as XQuery, have been
proposed which return their results in document order.
However, most recent efforts focused on query optimization
have either disregarded order or proposed a static labelling scheme
in which update issues are not addressed. Based on the preliminary
results from our previous work, this paper presents a fast
method to maintain document ordering for changing XML data.
Analysis of our method shows that it is more efficient
and scalable than our previously proposed method as well as
other related work, especially under various scenarios of updates. |
| 0316 |
Efficient Ordering for XML Data |
Damien K. Fisher, Franky Lam, William M. Shui, Raymond K. Wong
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: wong@cse.unsw.edu.au |
With the increasing popularity of XML, there arises
the need for managing and querying information in this
form. Several query languages, such as XQuery, have been
proposed which return their results in document order.
However, most recent efforts focused on query optimization
have disregarded order. This paper presents a simple yet
elegant method to maintain document ordering for XML data.
Analysis of our method shows that it is indeed efficient
and scalable, even for changing data. |
| 0315 |
On Clustering Schemes for XML Databases |
Damien K. Fisher, William M. Shui, Franky Lam, Raymond K. Wong
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: wong@cse.unsw.edu.au |
Although clustering problems are in general NP-hard, many research
efforts have been put in the areas of OODB and RDBMS. With the increasing
popularity of XML, researchers have been focusing on various
XML data management including query processing and optimization.
However, the clustering issues have been disregarded in
all their work. This paper provides a preliminary study on
data clustering for optimizing XML databases. Different clustering
schemes are compared through a set of extensive experiments. |
| 0314 |
Adaptive Change Management for Semi-structured Data |
Raymond K. Wong, Nicole Lam
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: wong@cse.unsw.edu.au |
This paper presents an efficient content-based version management
system for managing XML documents. Our proposed system uses complete
deltas for the logical representation of document versions.
This logical representation is coupled with an
efficient storage policy for version retrieval and insertion. Our
storage policy includes the conditional storage of complete document
versions (depending on the proportion of the document that was changed).
Based on the performance measure from experiments, adaptive scheme
based on non-linear regression is proposed.
Furthermore, we define a mapping between forwards and backwards deltas
in order to improve the performance of the system, in terms of both
space and time. |
| 0313 |
On Structural Inference for XML Data |
Raymond K. Wong, Jason Sankey
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: wong@cse.unsw.edu.au |
Semistructured data presents many challenges, mainly due to its lack
of a strict schema. These challenges are further magnified when large
amounts of data are gathered from heterogeneous sources. We address
this by investigation and development of methods to automatically infer
structural information from example data. Using XML as a reference
format, we approach the schema generation problem by application of
inductive inference theory. In doing so, we review and extend results
relating to the search spaces of grammatical inferences. We then
adapt a method for evaluating the result of an inference process from
computational linguistics. Further, we combine several inference
algorithms, including both new techniques introduced by us and those
from previous work. Comprehensive experimentation reveals our new
hybrid method, based upon recently developed optimisation techniques,
to be the most effective. |
| 0312 |
Efficient Query Relaxation for Semistructured Data |
Michael Barg, Raymond K. Wong
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: wong@cse.unsw.edu.au |
Semistructured data, such as XML, allows authors to structure a
document in a way which accurately captures the semantics of the data.
This, however, poses a substantial barrier to casual and non-expert
users who wish to query such data, as it is the data's structure
which forms the basis of all XML query languages. Without an accurate
understanding of this structure, users are unable to issue meaningful
queries. This problem is compounded when one realizes that data
adhering to different schema are likely to be contained within the
same data warehouse or federated database.
This paper describes a mechanism for meaningfully querying such data
with no prior knowledge of its structure. Our system returns approximate
answers to such a query over semistructured data, and can return useful
results even if a specific value cannot be matched. We discuss a number
of novel query processing and optimization techniques which enable us
to perform our query relaxation in near linear time. Experiments show
that our mechanism is very fast and scales well. |
| 0311 |
An Efficient WordNet-Based Summarizer for Large Text Documents |
Raymond K. Wong, Chit Sia
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: wong@cse.unsw.edu.au |
The current information overload problem has called for the need
to develop an automatic text summarization system. This paper
presents an efficient sentence-based
extraction summarizer which can be used for the above purpose.
Lexical chains were used as a basis and knowledge resources such
as WordNet and a sentence boundary disambiguation tool were
integrated to the system for better performance.
Three different summary extraction heuristics were used and
compared. An intrinsic evaluation which involved the comparison of
our summarizer with a commercial product to the human written
abstracts was performed. The results obtained have been
encouraging, and it is found that our system favors the human
judgement than the other system.
The algorithm used in this paper demonstrated a linear runtime
behavior. This not only suggests a positive position in the
scalability of our system but also its potentiality in handling
documents of longer length. |
| 0310 |
Update Synchronization for Mobile XML Data |
Franky Lam, Nicole Lam, Raymond K. Wong
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: wong@cse.unsw.edu.au |
Many handheld applications receive data from a primary
database server and operate in an intermittently
connected environment these days. They maintain data
consistency with data sources through sychronization.
In certain applications such as sales force automation,
it is highly desirable if updates on the data source can
be reflected at the handheld applications immediately.
This paper proposes an efficient method to synchronize XML
data on multiple mobile devices. Each device retrieves
and caches a local copy of data from the database
source based on a regular path expression. These local
copies may be overlapping or disjoint with each other.
An efficient mechanism is proposed to find all the disjoint
copies to avoid unnecessary synchronizations. Each update
to the data source will then be checked to identify all
handheld applications which are affected by the
update. Communication costs can be further reduced
by eliminating the forwarding of unnecessary operations to
groups of mobile clients. |
| 0309 |
"Variable Resolution Hierarchical RL" |
Bernhard Hengst |
The contribution of this paper is to introduce heuristics, that go
beyond safe state abstraction in hierarchical reinforcement learning, to
approximate a decomposed value function. Additional improvements in time
and space complexity for learning and execution may outweigh achieving
less than hierarchically optimal performance and deliver anytime
decision making during execution. Heuristics are discussed in relation
to HEXQ, a MDP partitioning that generates a hierarchy of abstract
models using safe state abstraction. The approximation methods are
illustrated empirically. |
| 0308 |
Safe State Abstraction and Discounting in Hierarchical
Reinforcement Learning |
Bernhard Hengst |
The great benefit in state abstraction for hierarchical reinforcement
learning (HRL) is the potential improvement in computational complexity
with significant compaction of the value function. Safe state
aggregation of reusable sub-task states is not possible in general for a
decomposed MDP using one decomposed discounted cumulative reward
function. This severely limits the effectiveness of HRL, particularly
for infinite horizon problems. This paper makes two related and novel
contributions: (1) the introduction of an additional supporting
decomposed discount function allowing state abstraction in the face of
discounting and (2) modifications to adapt HRL to solve infinite horizon
problems in which the recursively optimal policy may require a sub-task
to persist. |
| 0307 |
Itanium Page Tables and TLB |
Matthew Chapman, Ian Wienand, Gernot Heiser
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {matthewc, ianw, gernot}@cse.unsw.edu.au |
The Itanium architecture offers considerable flexibility in managing
the TLB. Besides features found in many architectures, such as TLB
tags and superpages, it supports two quite unusual features. One is
the choice of two hardware-walked page table formats, a linear array
and a hashed page table. The other is an unusual TLB tagging scheme
which, among others, allows a single TLB entry to map a page to
several address spaces, thus reducing the consumption of TLB entries
in the presence of sharing.
Only one page table format, the linear array, is presently supported
in Linux. However, this format neither supports the use of arbitrarily
mixed page sizes nor the sharing of TLB entries. We have implemented
the hashed page table format in Linux and found that this change has
negligible performance impact, which should pave the way for exploring
an implementation of superpage support. We have also implemented
sharing of TLB entries, and found that in normal Linux workloads the
effect is somewhere between negligible and a moderate performance
increase. We could, however, demonstrate that there are scenarios
where TLB sharing can produce significant performance gains. |
| 0306 |
Design and Performance analysis of CBCSWFQ packet scheduling
algorithm. |
Fariza Sabrina and Sanjay Jha
School of Computer Science and Engineering
The University of New South Wales, NSW 2052, Australia
Email: {farizas;Sjha}@cse.unsw.edu.au |
In active and programmable networks, packet processing could be
accomplished in the router within the data path. For efficient resource
allocation in such networks, the packet scheduling schemes should
consider multiple resources such as CPU and memory in addition to the
bandwidth to improve overall performance. The dynamic nature of network
load and the inherent unpredictability of processing times of active
packets pose a significant challenge in CPU scheduling. It has been
identified that unlike bandwidth scheduling, prior estimation of CPU
requirements of a packet is very difficult since it is platform
dependent and it also depends on processing load at the time of
execution and operating system scheduling etc. This paper presents a new
composite scheduling algorithm called CBCSWFQ which is based on Weighted
Fair Queuing (WFQ) and is designed for scheduling both bandwidth and CPU
resources adaptively, fairly and efficiently. CBCSWFQ uses an adaptive
prediction technique for estimating the processing requirements of
active flows efficiently and accurately. Through simulation and analysis
works we show the improved performance of our scheduling algorithm in
achieving better delay guarantees compared to WFQ if used separately for
CPU and Bandwidth scheduling. |
| 0305 |
An Efficient Resource Management Framework for
Programmable and Active Networks. |
Fariza Sabrina and Sanjay Jha
School of Computer Science and Engineering
The University of New South Wales, NSW 2052, Australia
Email: {farizas;Sjha}@cse.unsw.edu.au |
This report presents a framework for resource management in highly
dynamic active and programmable networks. The goal is to allocate and
manage node resources in an efficient way while ensuring effective
utilization of network and supporting load balancing. The framework
supports co-existence of active and non-active nodes and proposes a
novel Directory Service (DS) architecture that can be used to discover
the suitable active nodes in the Internet and for selecting best network
path (end-to-end) and reserving the resources along the selected path.
Intra-node and inter-node resource management are facilitated through
the DS, while within an active node the framework implements a composite
scheduling algorithm to schedule CPU and bandwidth resources to resolve
the combined resource scheduling problems. In addition, a flexible
active node database system has been introduced in order to resolve the
challenging problem of determining the CPU requirement of the incoming
packets. Through simulation we show the improved performance of our
scheduling algorithm in achieving overall fairness in allocating active
node resources. |
| 0304 |
A Formal Approach to Interface Synthesis for SoC Design |
Vijay D'silva
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: vijayd@cse.unsw.edu.au |
Systems-on-Chip (SoC) design methodologies rely increasingly on
reuse of intellectual property (IP) blocks. IP reuse is a labour intensive
and time consuming process as IP blocks often have different
communication interfaces. We present a framework to
generate a synthesizable VHDL description of an interface between two
mismatching IP communication protocols. We improve and extend
previously published work by formalising the problem and by
explicitly handling data width and type mismatching and
multiple data transfers. At present, simpler cases of pipelining are
handled as well. We have implemented our technique and demonstrate it
by generating an interface between the CoreConnect Processor Local Bus
from IBM and the AMBA System Bus from ARM. |
| 0303 |
Towards Unstrusted Device Drivers |
Ben Leslie, Gernot Heiser
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {benjl, gernot}@cse.unsw.edu.au |
Device drivers are well known to be one of the prime sources of
unreliability in today's computer systems. We argue that this need not
be, as drivers can be run as user-level tasks, allowing them to be
encapsulated by hardware protection. In contrast to prior work on
user-level drivers, we show that on present hardware it is possible to
prevent DMA from undermining this encapsulation. We show that this can
be done without unreasonably impacting driver performance. |
| 0302 |
Invented Predicates to Reduce Knowledge Acquisition Effort |
Hendra Suryanto and Paul Compton
Artificial Intelligence Department
School of Computer Science and Engineering,
The University of New South Wales Sydney 2052, Australia |
The aim of this study was to develop machine learning techniques that would speed up
knowledge acquisition from an expert. As the expert provided knowledge the system would
generalize from this knowledge in order to reduce the need for later knowledge acquisition.
This generalization should be completely hidden from the expert. We have developed such a
learning technique based on Duce's intra construction operator and absorption operators
(Muggleton, 1990) and applied to Ripple Down Rules (RDR) incremental knowledge acquisition
(Compton & Jansen, 1990). Preliminary evaluation shows that knowledge acquisition can be
reduced by up to 50%. |
| 0301 |
Parallelized FTP |
Shaleeza Sohail, Sanjay Jha and Hossam ElGindy
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {sohails,sjha,elgindyh}@cse.unsw.edu.au |
The parallelized FTP (P-FTP) approach, attempts to solve the problem
of slow downloads of large multimedia files while optimizing the
utilization of mirror servers. The approach presented in this paper
downloads a single file from multiple mirror servers simultaneously,
where each mirror server transfers a portion of the file. The P-FTP server
calculates the optimum division of the file for effecient transfer.
The dynamic monitoring ability of P-FTP maintains the file transfer
process at the optimized level no matter how abruptly network and mirror
server characteristics change. |
| 0216 |
Avoiding Useless Packet Transmission for Multimedia over IP Networks: The Case of Multiple Multimedia Flows |
Jim Wu and Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {jimw,mahbub}@cse.unsw.edu.au |
In this paper, we investigated UPT avoidance problem with multiple
multimedia flows. We propose a management module, called
Unintelligible Flow Management (UFM), to enhance UPTA in networks with
multiple multimedia flows. We have proposed two different management
policies for UFM, i.e. Random Select (RS) and Least Bandwidth Select
(LBS). We have demonstrated incorporation of RS/LBS into WFQ, and
evaluated the effectiveness of both RS and LBS under various network
scenarios (e.g. single/multiple congested links,
homogeneous/heterogeneous video applications, etc.). Simulation
results show that UFM can significantly improve TCP throughput and
average video intelligibility index, as compared with plain WFQ. On
the other hand, our simulation results also suggest that RS and LBS
have similar performance with homogeneous multimedia
applications. However, with heterogeneous multimedia applications, LBS
yields better performance, in terms of total number of video flows
recovered and average intelligibility index of video applications. |
| 0215 |
Avoiding Useless Packet Transmission for Multimedia over IP Networks: The Case of Multiple Congested Links |
Jim Wu and Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {jimw,mahbub}@cse.unsw.edu.au |
In this paper, we investigate UPT avoidance problem with multiple
congested links. We propose three different UPTA enforcement schemes
--- basic UPTA (B-UPTA), Partial UPTA (P-UPTA) and Centralised UPTA
(C-UPTA). The challenge of UPT avoidance with multiple congested links
is to determine global fairshare and enforce UPTA based on the global
fairshare. We proposed the Bottleneck Fairshare Discovery (BFD)
protocol to address this issue. BFD is a feedback mechanism proposed
to assist UPTA in networks with multiple congested links. We describe
the implementation of BFD with UPTA, taking WFQ as an example. Our
simulation study shows that B-UPTA fails to detect UPT in some
situations. P-UPTA can eventually detect UPT, but bandwidth may have
been wasted on upstream links before UPT is detected. C-UPTA can avoid
UPT in all situations, as it always drops useless packets at network
edge. Simulation results suggest that, with C-UPTA, the achieved TCP
throughput improvement is very close to the maximum theoretical
value. In the paper, we also analyse the performance of C-UPTA
quantitatively, in terms of TCP throughput, file download time, impact
on video intelligibility, and impact on fairness. Our simulation
results reveal that, for all six scenarios, the TCP throughput has
been significantly improved (with improvement factor up to 50%). As a
result, file download times (for various file size) have been greatly
reduced (more than 30%). On the other hand, incorporation of C-UPTA
into WFQ has no significant impact on intelligibility of the MPEG-2
video (with a difference less than 3%). For all six scenarios, C-UPTA
maintains fairness which is comparable to WFQ. This proves that UPTA
does not have any adverse impact on fairness performance of fair
algorithms. |
| 0214 |
A Constructive Proof of the Turing Completeness of Circal |
J\'er\'emie Detrey
ENS Lyon
46, all\'e d'Italie
69 364 Lyon cedex 07, France
e-mail: jdetrey@ens-lyon.fr
Oliver Diessel
School of Computer Science and Engineering
University of New South Wales
Sydney, NSW 2052, Australia
e-mail: odiessel@cse.unsw.edu.au |
This paper gives a proof of the Turing completeness of the
Circal process algebra by exhibiting a universal program capable of
mapping any Turing machine description into Circal specifications that
effectively simulate the behaviour of the given machine. |
| 0213 |
SCCircal: a Static Compiler Mapping XCircal to Virtex FPGAs |
J\'er\'emie Detrey
ENS Lyon
46, all\'e d'Italie
69 364 Lyon cedex 07, France
e-mail: jdetrey@ens-lyon.fr
Oliver Diessel
School of Computer Science and Engineering
University of New South Wales
Sydney, NSW 2052, Australia
e-mail: odiessel@cse.unsw.edu.au |
This paper describes the new version of SCCircal, a static
compiler for XCircal targeted to Xilinx Virtex architecture. This
compiler, written in Java, is now capable of providing a real FPGA
implementation for almost any Circal process specification. Thus it
supports hierarchy, abstraction and relabelling. This paper also
introduces the notion of a process interface, provided to help the
development of further extensions of this compiler. |
| 0210 |
A Theory of Compositional Concurrent Objects |
Xiaogang Zhang and John Potter
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: {xzhang,potter}@cse.unsw.edu.au |
This paper presents the theory of composition for concurrent object
systems, based on an object modelling in the \kappa-calculus. The
behaviour of a concurrent object can be modelled as the composition of
a process representing the functional behaviour of the object with no
constraint on its concurrent interactions, or synchronisation, and a
process representing concurrency constraints to reduce the allowable
concurrency and to avoid the states of exception. With this model, we
use the \kappa-calculus, a process algebra with polars, to study the
theory of composition of concurrent behaviours, investigate when and
how concurrent behaviours can (or should) be composed with and
separated from functional behaviours or other concurrent behaviours,
identify relevant patterns and properties of concurrent behaviours,
etc. Some generic properties of the behaviour composition, such the
Identity Law and Associative Law, have been proven in this study.
Keywords: object models, \kappa-calculus, \pi-calculus, concurrency
constraints, concurrency controls, composition, synchronisation |
| 0209 |
A Fast and Versatile Path Index for Querying Semi-Structured Data |
Michael Barg
Raymond. K. Wong
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
Email: {mbarg, wong}@cse.unsw.edu.au |
The richness of semi-structured data allows data of varied and inconsistent
structures to be stored in a single database. Such data can be represented
as a graph, and queries can be constructed using path expressions, which
describe traversals through the graph.
Instead of providing optimal performance for a limited range of path
expressions, we propose a mechanism which is shown to have consistent and
high performance for path expressions of any complexity, including those
with descendant operators (path wildcards). We further detail mechanisms
which employ our index to perform more complex processing, such as evaluating
both path expressions containing links and entire (sub) queries containing
path based predicates.
Performance is shown to be independent of the number of terms in the path
expression, even where these contain wildcards. Experiments show that our
index is faster than conventional methods by up to two orders of magnitude
for certain query types, is small, and scales well. |
| 0208 |
Design and Implementation of a Virtual Quality of Service MAC Layer (VQML) for Wireless LANs |
Mahbub Hassan, Kenneth Lee, Mohammad Rezvan
School of Computer Science and Engineering
The University of New South Wales
Sydney 2052, Australia |
Wireless LANs are becoming increasingly popular. While the technology
offers wireless connectivity, it offers minimal or no quality of
service (QoS) to multimedia applications. We propose a virtual QoS MAC
layer (VQML) between MAC and networking layers to provide QoS. The
proposed VQML architecture is implemented in a Linux platform and
tested in an experimental wireless network test-bed in the Network
Research Laboratory of UNSW. |
| 0207 |
Active Protocol Label Switching (APLS) |
William Lau and Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: wlau,sjha@cse.unsw.edu.au |
Modern layer 3 networking technologies have mainly been designed for performance and for network providers. This report proposes a new network architecture called Active Protocol Label Switching (APLS) that combines the performance of current label switching technology with novel concepts that cultivate service provisioning. Novel features such as Virtual Label Space, APLS micro-instruction architecture, and micro-policy based forwarding provide a more powerful network model, facilitate better network level service engineering, and give tremendous flexibility to both network and service providers.
The thrust of our study is to construct an APLS test-bed using open hardware and software
and later use this test-bed for experimenting various features/options available with APLS.This report also describes our prototype implementation of APLS under Linux. |
| 0206 |
The Survey of Bandwidth Broker |
Shaleeza Sohail and Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {sohails,sjha}@cse.unsw.edu.au |
Keeping in mind the present network management research trends, it can
be safely stated that in the near future enterprise networks and ISPs
will need a network management entity to dynamically manage QoS
networks. DiffServ is one of the emerging networks that introduces
bandwidth broker as its logical resource, network and policy
management module. Due to the complex and huge functionality provided
by bandwidth broker, it has very large number of semi explored
research areas. This survey is an effort to briefly discuss some of
the developments in the ongoing process of defining and implementing a
functional bandwidth broker. |
| 0205 |
The Responsive Bisimulations in the \kappa-calculus |
Xiaogang Zhang and John Potter
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: {xzhang,potter}@cse.unsw.edu.au |
This paper presents responsive bisimulation in the \kappa-calculus. It
is a part of the ongoing work attempts to model concurrent object
systems using process algebra. The behaviour of an object can be
described as the composition of a process representing the basic
functionality of the object and separate processes controlling the
concurrent behaviour of that object. While familiar usually failed,
the responsive bisimulation proposed by the authors in an earlier
paper where the delaying a message locally and remotely have the same
effect as long as potential interference by competing receptors is
avoided, is able to capture the behavioural equivalence between object
components. With this bisimulation, an equivalence between the
\pi-calculus expression (\nu n)(m.\bar{n}|k.n.P) and k.m.P then can be
achieved. However, in the earlier paper, the responsive bisimulation
was described in the polar \pi-calculus, which added a few improved
features for modelling concurrent objects while maintains the
syntatical simplicity similar to the normal \pi-calculus, but is still
difficult to express general behaviurs of concurrent objects
efficiently. The \kappa-calculus, where locks are included as
primitive, in the other hand, is more expressive and flexible in
modelling compositional concurrenct objects. This paper presents
responsive bisimulation in the \kappa-calculus, and therefore will
form an improved base for studies on both the theory of behaviours
composition and the semantics of compositional concurrent OO
programming languages. |
| 0204 |
A Constraint Description Calculus for Compositional Concurrent Objects |
Xiaogang Zhang and John Potter
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: {xzhang,potter}@cse.unsw.edu.au |
This report presents the \kappa-calculus, a mobile-process algebra
with lock as primitive. The Guarded Conditional Exclusive Choice
"\otimes", together with a selective locking/unlocking mechanism, is
used in the \kappa-calculus as the only combineter for input guared
processes. Therefore, for input guarded terms, the standard mutually
exclusive choice "+" of CCS or \pi-calculus, and the parallel
composition "|", become two extreme cases of the unified combinerer
"\otimes". The \kappa-calculus can provide a simpler, clearer and more
composible description of the method exclusion in the modelling of
concurrent objects, while preserves other powers of the \pi-calculus
in modelling the mobility of concurrent objects. An concurrent object
may be modelled in the \kappa-calculus as either a single object
process or the composition of a function object proecess and a set of
control object processes. A single object process modelled in the
\kappa-calculus has a generic form \Lambda}\circ[G\ll\tilde{M}\gg}],
where \Lambda records the statues of lock, G decribes the methods
exclusion and \tilde{M} is a set of processes each of which presents
the functional behaviour of a method body. The \kappa-calculus
provides a straightforward model to separate aspects such as object
functionality, method exclusion and locking schema and states in a
high level abstraction, and provides semantic for a compositional
concurrent object-oriented programming language. |
| 0203 |
The Responsive Bisimulations in the polar \pi-calculus |
Xiaogang Zhang and John Potter
School of Computer Science and Engineering
University of New South Wales, Australia
E-mail: {xzhang,potter}@cse.unsw.edu.au |
Ongoing work attempts to model concurrent object systems using process
algebra. The behaviour of an object can be described as the
composition of a process representing the basic functionality of the
object and separated processes controlling the concurrent behaviour of
that object. However, familiar bisimulations, including the weak
barbed equivalence, are too strong to capture the behavioural
equivalence between object components. This paper proposes the
responsive bisimulation, an even weaker bisimulation relation which
considers that delaying an incoming message locally has the same
effect as delaying it externally, as long as potential interference by
competing receptors is avoided. With this bisimulation, an equivalence
between the \pi-calculus expression (\nu n)(m.\bar{n}|k.n.P) and k.m.P
then can be achieved. The responsive bisimulation is congruence for
the family of processes which model objects. |
| 0202 |
Avoiding Useless Packet Transmission for Multimedia over IP Networks: The Case of Single Congested Link |
Jim Wu and Mahbub Hassan
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {jimw,mahbub}@cse.unsw.edu.au |
When packet loss rate exceeds a given threshold, received audio and video
become unintelligible. A congested router transmitting multimedia packets, while
inflicting a packet loss rate beyond a given threshold, effectively transmits
useless packets. Useless packet transmission wastes router bandwidth when it is needed
most. We propose an algorithm to avoid transmission of useless multimedia packets, and
allocate the recovered bandwidth to competing TCP flows. We show that the proposed
algorithm can be easily implemented in well-known WFQ and CSFQ fair packet queueing and
discarding algorithms. Simulation of a 15-second MPEG-2 video clip over a congested
network shows that the proposed algorithm effectively eliminates useless packet transmission,
and as a result of that significantly improve throughput and file download times of
concurrent TCP connections. For the simulated network, file download time is reduced by 55%
for typical HTML files, 36% for typical image files, and up to 30% for typical video
files. A peak-signal-to-noise-ratio (PSNR) based analysis shows that the overall
intelligibility of the received video is no worse than that received without the
incorporation of the proposed useless packet transmission avoidance algorithm.
Our fairness analysis confirms that implementation of our algorithm into the fair
algorithms (WFQ and CSFQ) does not have any adverse effect on the fairness performance
of the algorithms. |
| 0201 |
Design and Implementation of the L4 Microkernel for Alpha Multiprocessors |
Daniel Potts, Simon Winwood, Gernot Heiser
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {danielp,sjw,gernot}@cse.unsw.edu.au |
This report gives an overview of the techniques used in the
multiprocessor implementation of the L4 microkernel on the Alpha
processor family. The implementation is designed to be scalable to a
large number of processors, which is supported by keeping kernel data
processor-local as much as possible, and minimising the use of spinlocks
and inter-processor interrupts. |
| 0112 |
An Efficient IP Matching Tool using Forced Simulation |
Partha Roop
Department of EEE
University of Auckland, New Zealand
p.roop@auckland.ac.nz
A. Sowmya
School of CSE
University of New South Wales, Australia
sowmya@cse.unsw.du.au
S. Ramesh
Department of CSE
Indian Institute of Technology, Bombay, India
ramesh@cse.iitb.ac.in
Haifeng Guo
Department of CS
State University of New York
Stony Brook, NY 11794-4400
haifeng@cs.sunysb.edu |
Automatic IP (Intellectual Property) matching is a key to reuse of IP cores. This report presents an efficient IP matching algorithm which can check if a given programmable IP can be {\em adapted} to match a given specification. When such adaptation is possible, the algorithm also generates a device driver (an interface) to adapt the IP. Though simulation, refinement and bisimulation based algorithms exist, they cannot be used to check the adaptability of an IP, which is the essence of reuse. The IP matching algorithm is based on a formal verification technique called {\em forced simulation}. A forced simulation based matching algorithm is implemented using a logic programming environment, which provides distinct advantages for encoding such an algorithm.The prototype tool, MatchMaker, has been used to reuse several programmable IPs achieving on an average 12 times speedup and 64 \% reduction in code size in comparison to previously published algorithm. |
| 0111 |
Towards Patterns of Web Services Composition |
Boualem Benatallah
School of Computer Science
University of New South Wales, Sydney NSW 2052 Australia
Email: boualem@cse.unsw.edu.au |
The ability to efficiently and effectively share services on the Web
is a critical step towards the development of the on-line economy.
Virtually every organisation needs to interact with manifold other
organisations in order to request their services. Reciprocally, an
organisation providing a service is often required to interact with a
large and dynamic set of service requestors. The lack of high level
abstractions and functionalities for Web service integration has
triggered a considerable amount of research and development efforts.
This has resulted in a number of products, standards, frameworks and
prototypes addressing sometimes overlapping, sometimes complementary
aspects of service integration.
In this report we summarise some of the challenges and recent
developments in the area of Web service integration, and we abstract
some of them in the form of software design patterns. Specifically we
present patterns for both bilateral service-based interactions,
multilateral service composition, and execution of composite services
both in a centralised and in a fully distributed environment. The
report also shows how these patterns map into a variety of
implementation technologies including object-based approaches (e.g.
CORBA and EJB), EAI and ERP suites, cross-enterprise workflows, EDI
and XML-based B2B frameworks. |
| 0110 |
A Dynamically-Balanced Walking Biped |
Graham Mann*, Bruce Armstrong*, Phil Preston**, Barry Drake**
* School of Information Technology
Murdoch University
South Street Murdoch 6050 Australia
** School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: g.mann@murdoch.edu.au b.armstrong@murdoch.edu.au
philp@cse.unsw.edu.au bdrake@cse.unsw.edu.au |
Describes the mechanical, electronic and software design of a 10-DOF
bipedal robot which has been constructed to study control,
parameterisation and automatic expansion of the stability envelope of a
complex real-time behaviour, namely, dynamically-balanced two-legged
walking. The machine is physically complete and demonstrates reasonable
reliability in movement control including dynamically-balanced standing.
High-level reinforcement learning code is being developed to extend this
to walking. The machine offers a challenging problem domain to the
flourishing machine learning community and represents a shift in
emphasis, away from learning algorithms that work on simplified,
preprocessed, artificial and static data sets to learning heuristics
which deal with noisy, real-time data collected from sensors on a
dynamic, real-world system. |
| 0109 |
Let's Study Whole-Program Cache Behaviour Analytically |
Xavier Vera and Jingling Xue
Xavier Vera
Institutionen fur Datateknik
Malardalens Hogskola
Vasteras, Sweden
E-mail: xavier.vera@mdh.se
Jingling Xue
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: jxue@cse.unsw.edu.au |
Based on a new characterisation of data reuse across multiple loop nests,
we present a method, an implementation and experimental results for analysing
the cache behaviour of whole programs with regular computations. Validation
against cache simulation using real codes confirms the efficiency and accuracy
of our method. The largest program we have analysed, Applu from SPECfp95, has
3868 lines, 16 subroutines and 2565 references. Assuming a 32KB cache with a
32B line size, our method obtains the miss ratio with an absolute error of
about 0.8% in about 128 secs while the simulator used runs for nearly 5 hours
on a 933MHz Pentium III PC. Our method can be used to guide compiler
locality optimisations and improve cache simulation performance. |
| 0108 |
Self-Coordinated and Self-Traced Composite Services
with Dynamic Provider Selection |
B. Benatallah(*), M. Dumas(**), M.-C. Fauvet(*) and H. Paik(*)
(*) School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: mcfauvet@cse.unsw.edu.au
(**) Cooperative Information Systems Research Centre
Queensland University of Technology
GPO Box 2434, Brisbane QLD 4001 |
The growth of Internet technologies has unleashed a wave of
innovations that are having tremendous impact on the way organisations
interact with their partners and customers. It has undoubtedly opened
new ways of automating Business-to-Business (B2B)
collaboration. Unfortunately, as electronic commerce applications are
most likely autonomous and heterogeneous, connecting and coordinating
them in order to build inter-organisational services is a difficult
task. To date, the development of integrated B2B services is
largely ad-hoc, time-consuming and requires an enormous effort of
low-level programming. This approach is not only tedious, but also
hardly scalable because of the volatility of the Internet, and the
dynamic nature of business alliances. In this paper, we consider the
efficient composition and execution of B2B services. Specifically, we
present a framework through which services can be declaratively
composed, and the resulting composite services can be executed in a
\textit{decentralised} way within a dynamic environment. The
underlying execution model supports the incremental collection of the
execution trace of each composite service instance. These traces are
particularly useful for customer feedback, and for detecting
malfunctionings in the constitution of a composite service. |
| 0107 |
Analysing Cache Memory Behaviour for Programs with IF Statements |
Xavier Vera and Jingling Xue
Xavier Vera
Institutionen fur Datateknik
Malardalens Hogskola
Vasteras, Sweden
E-mail: xavier.vera@mdh.se
Jingling Xue
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: jxue@cse.unsw.edu.au |
Cache memories are widely used to hide the increasing gap between main memories
and processors speed. Several methods have been proposed to analyse their
behaviour in order to increase their performance. Many of those methods have
been based on trace-driven simulators, which are quite slow and do not give all
the information needed by the compilers. Analytical methods have been developed
to overcome these problems. Unfortunately, one of the main drawbacks is that
they can not analyse codes with IF statements.
We propose an analytical method that analyses perfectly nested loops with IF
statements. Applying compiler techniques such as loop sinking allows us to
analyse imperfectly nested loops as well. We have analysed different benchmarks,
including SPECfp, Perfect Suite, Livermore kernels and Linpack. Our analysis
shows that we can analyse 17\% more loop nests, obtaining very accurate results. |
| 0106 |
Code Search based on CVS Comments: A Preliminary Evaluation |
Annie Chen, Yun Ki Lee, Andrew Y. Yao, Amir Michail
School of Computer Science and Engineering,
The University of New South Wales, Sydney 2052, Australia,
{anniec,s2251001,andrewy,amichail}@cse.unsw.edu.au |
We have built a tool, CVSSearch, that searches for fragments of source
code by using CVS comments. (CVS is a version control system that is
widely used in the open source community.) Our search tool takes
advantage of the fact that a CVS comment typically describes the lines
of code involved in the commit and this description will typically
hold for many future versions. This paper provides a preliminary
evaluation of this technique by 74 students at the University of New
South Wales. Among our findings, CVS comments do provide a valuable
source of information for code search that complements --- but does
not replace --- tools that simply search the source code itself (e.g., grep). |
| 0105 |
A Platform for Portable and Embedded Systems Research |
Adam Wiggins
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: awiggins@cse.unsw.edu.au |
The PLEB project is a student run project aimed at stimulating portable &
embedded systems research within the school. This report outlines the projects
activities and some of the experiences gained in developing the first hardware
platforms. The report also sketches the details for second generation PLEB
hardware platforms and the project's future direction. |
| 0104 |
L4 Reference Manual --- Alpha 21x64 |
Daniel Potts, Simon Winwood and Gernot Heiser
School of Computer Science and Engineering,
The University of New South Wales, Sydney 2052, Australia,
{danielp,sjw,gernot}@cse.unsw.edu.au |
This document describes release 2.0 of the L4 microkernel for the Alpha
microprocessor family. The kernel ABI is mostly compatible with the MIPS
R4x00 version, but provides full multiprocessor support. |
| 0103 |
A Component Architecture for System Extensibility |
Antony Edwards and Gernot Heiser
School of Computer Science and Engineering,
The University of New South Wales, Sydney 2052, Australia,
{antonye,gernot}@cse.unsw.edu.au |
Component-based programming has shown itself to be a natural way of
constructing extensible software. Well-defined interfaces,
encapsulation, late binding and polymorphism promote extensibility,
yet despite this synergy, components have not been widely employed at
the systems level. This is primarily due to the failure of existing
component technologies to provide the protection and performance
required of systems software. This thesis presents the design,
implementation and performance of a component model for system
extensions that allow users to to create and customise system
services.
Effective access control is a crucial feature of any system. In an
extensible system, however, where potentially any user can create and
modify system services, access control is even more critical. Despite
the increasing importance of access control due to extensibility and
increased connectivity, the protection mechanisms provided by existing
component systems remain primitive and ad hoc. This thesis presents
the design, implementation and performance of a complete access
control model for extensible systems. |
| 0101 |
CVSSearch: Searching through Source Code using CVS Comments |
Annie Chen, Eric Chou, Joshua Wong, Andrew Y. Yao, Qing Zhang,
Shao Zhang, Amir Michail
School of Computer Science and Engineering,
The University of New South Wales, Sydney 2052, Australia,
{anniec,tzuchunc,joshuaw,andrewy,qzha132,shaoz,amichail}@cse.unsw.edu.au |
CVSSearch is a tool that searches for fragments of source code by using
CVS comments. CVS is a version control system that is widely used in
the open source community. Our search tool takes advantage of the
fact that a CVS comment typically describes the lines of code involved in
the commit and this description will typically hold for many future
versions. In other words, CVSSearch allows one to better search the most
recent version of the code by looking at previous versions to better
understand the current version. |
| 0007 |
Jigsaw: the unsupervised construction of spatial representations |
Mark W. Peters and Barry Drake
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: markpeters@cse.unsw.edu.au bdrake@cse.unsw.edu.au |
A fundamental assumption in machine vision is that the spatial arrangement of
pixels is given. In challenging this assumption we have utilised a general
relationship that exists between space and behaviour. This relationship
presents itself as spatial redundancy, which other researchers have considered
problematic. We present a mathematical model and empirical investigations into
this relationship and develop an algorithm, JIGSAW, which uses it to build
spatial representations. The philosophy underpinning JIGSAW takes signal
behaviour, rather than position, as primary. JIGSAW is an unsupervised
learning algorithm that is efficient in time and space and that makes minimal
assumptions about its operating domain. This algorithm offers engineering
potential, opportunities in the understanding of biological vision, and a
contribution to the wider field of cognitive science. |
| 0006 |
EPDL: A Logic for Causal Reasoning |
Dongmo Zhang and Norman Foo
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: dongmo@cse.unsw.edu.au, norman@cse.unsw.edu.au |
This paper is twofold. First, we presentes an extended system $EPDL$ of
propositional dynamic logic by allowing a proposition as a modality in order
to represent and specify indirect effects of actions and causal propagation.
An axiomatic deductive system is given which is sound and complete with
respect to the corresponding semantics. The resultant system provides a
unified treatment of direct and indirect effects of actions. Second, we
reduce the $EPDL$ into a mutlimodal logic by deleting the component of
action in order to obtain an axiomatized logical system for causal
propagation. A characterization theorem of the logic is given. Properties of
causal reasoning with the logic are discussed. |
| 0005 |
Specifications for End to End IP Rate Control (Version 1.0) |
Abdul Aziz Mustafa, Mahbub Hassan and Sanjay Jha
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {amustafa,mahbub,sjha}@cse.unsw.edu.au |
Currently no network-level flow control exists in the IP-based networks.
In a recent paper[Adcom2000], we proposed a network-level flow control
architecture, called End-to-End IP Rate Control. The motivation behind
IP Rate Control is to provide a new network service which will provide
users fast access to any unused network resources (buffer space, link
bandwidth). This report details the specifications of the IP Rate
Control architecture which can be used to implement the service in a
given networking platform. |
| 0004 |
A Formal Approach to Component Based Development of Embedded Systems |
Partha S. Roop, A. Sowmya
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {proop,sowmya}@cse.unsw.edu.au
S. Ramesh
Department of Computer Science and Engineering
Indian Institute of Technology
Bombay, India - 400 076
E-mail: ramesh@cse.iitb.ernet.in |
Component reuse techniques have been the recent focus of research as
they are seen as the next generation techniques to handle increasing
system complexities. However, there are several unresolved issues to be
addressed and prominent among them is the issue of component matching. As
the number of reusable components in a component database grows, the
task of manually matching a component to the user requirements will be
infeasible. Automating this matching can help in rapid system prototyping,
improve quality and reduce cost. In addition, if the matching algorithm
is sound, this approach can also reduce precious validation effort.
In this paper, we propose an algorithm for automatic matching of a design
function to a device from a component database. The distinguishing feature
of the algorithm is that when successful, it generates an interface
which can automatically adapt the device to behave as the function.
The algorithm is based on a new simulation relation called forced
simulation which is shown to be a necessary and sufficient condition
for component matching to be possible for a given pair of function and
device. We demonstrate the application of the algorithm by reusing two
system level Intel chips. |
| 0003 |
The Logical Validation of Mathematical Diagrammatic Proofs |
Christina L. Jenkin
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: tina@alum.rpi.edu |
Diagrams have been used for problem solving for thousands of years but
have only recently had a resurgence into mainstream science with
applications in cognitive science, artificial intelligence, computer
science, physics, mathematics, and other disciplines. Diagrammatic
reasoning has been defined as ``the understanding of concepts and
ideas by the use of diagrams and imagery, as opposed to linguistic or
algebraic representations.'' This paper aims to introduce the reader
to diagrammatic reasoning, specifically in the area of diagrammatic
proofs and logically validate the soundness of the construction steps
in a diagrammatic proof, with hopes of helping to develop a
theoretical basis for computing directly with diagrammatic
representations. This will be accomplished through an analysis of
diagrammatic proofs of geometric theorems and a study of some
problematic proofs in this area. In addition, a proof showing the
equivalence of the two current solutions to the problem of
generalization and a link between traditional theories of computation,
such as fixed points, invariants, and continuations, with diagrammatic
proofs is shown. In essence, this paper intends to help advance the
understanding of what is involved in diagrammatic proofs, why they
work, and why they sometimes do not work as well as show that diagrams
alone can be regarded as legitimate (or even desirable) proofs in the
area of geometric theorems. Hopefully, this will help to open new
opportunities for study and development in the justification and in
later work on the automation of diagrammatic proofs. |
| 0001 |
Measure for Vector Approximation |
Benjamin Briedis
The School of Computer Science & Engineering
The University of New South Wales
UNSW Sydney 2052
Australia
E-mail: bbriedis@cse.unsw.edu.au |
The creation of approximations for vectors for use in similarity searching
(also known the retrieval of the k-nearest neighbours) is examined.
A measure is derived that is suitable for judging the quality
of a set of vector approximations. This measure is used in the modification
of a technique used in similarity searching known as the VA-file. The
modified VA-file is evaluated, and a clear improvement in performance is
demonstrated. |
| 9908 |
An approach to formalising relationships between speaker-relative and absolute spatial reference systems |
Jane Brennan, William Wilson
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {jbrennan,billw}@cse.unsw.edu.au |
There has been extensive empirical research in cognitive linguistics
exploring different reference systems used to describe spatial situations
across different cultures. It has been suggested that speaker relative
and absolute spatial reference systems seem to be interchangeable. This
report discusses speaker-relative and absolute spatial reference systems
in terms of left-right systems and cardinal directions. An approach to
formalising some of the relationships between both systems is proposed. We
plan to provide an extension to this limited formalisation in a way
which could enable automatic interchangeability between the systems of
reference discussed within the (Human-Computer) interface of Geographic
Information Systems. Natural language interfaces to navigation systems
could be a very interesting application of such an extended formalisation.
Keywords: Spatial Reasoning, Cognitive Structure of Spatial Knowledge, Spatial Reference Systems |
| 9907 |
"Boosting" Stumps from Positive Only Data |
Andrew R. Mitchell
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: andrewm@cse.unsw.edu.au |
Most current learning algorithms require both positive and negative data.
This is also the case for many of the recent ensemble learning techniques.
Applications of boosting, for example, rely on both positive and
negative data to produce a hypothesis with high predictive accuracy.
In this technical report, a learning methodology is presented that does
not rely on negative examples. A learning method in this framework
is described which shows remarkable similarities to boosting stumps.
This is all the more surprising because learning from positive data has
traditionally turned out to be very difficult.
Empirical results show that this technique successfully boosts stumps
from positive data by paying only a small price in accuracy compared to
learners that have access to both positive and negative data.
Some theoretical justification of the results is also provided. |
| 9906 |
Fast Address-Space Switching on the StrongARM SA-1100 Processor |
Adam Wiggins, Gernot Heiser
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {awiggins,gernot}@cse.unsw.edu.au |
The StrongARM SA-1100 is a high-speed low-power processor aimed at
embedded and portable applications. Its architecture features virtual
caches and TLBs which are not tagged by an address-space
identifier. Consequently, context switches on that processor are
potentially very expensive, as they may require complete flushes of TLBs
and caches.
This report presents the design of an address-space management technique
for the StrongARM which minimises TLB and cache flushes and thus
context switching costs. The basic idea is to implement the top-level of
the (hardware-walked) page-table as a cache for page directory entries
for different address spaces. This allows switching address spaces with
minimal overhead as long as the working sets do not overlap. For small
(<=32MB) address spaces further improvements are possible by
making use of the StrongARM's re-mapping facility. Our technique is
discussed in the context of the L4 microkernel in which it will be
implemented. |
| 9905 |
Splice-2 Comparative Evaluation: Electricity Pricing |
Michael Harries
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: mbh@cse.unsw.edu.au |
Splice-2 is a machine learning method designed for batch learning in
domains with hidden changes in context. This report characterises the
performance of Splice-2 on a real world dataset in comparison with C4.5,
an on-line learner (emulated by C4.5), and an unsupervised learning system.
Two experiments are reported, both using electricity prices from the
Australian state of New South Wales as the classification domain. The
first experiment uses permutations of the dataset to explore the
difficulties of using C4.5 to either identify hidden contexts, or to
achieve the same accuracy as Splice-2 on this domain. The dataset
permutations are also used to characterise some strengths and
weaknesses of Splice-2. The second experiment uses permutations of an
extended dataset from the same domain to examine, for both C4.5 and
Splice-2, the effects of adding additional known attributes.
We find that C4.5 cannot induce the hidden contexts found by Splice-2.
Further, Splice-2 generally provides more accurate results than C4.5.
The exceptions occur when the order of the dataset is destroyed, or
where new attributes are very similar to time. The best results from
C4.5 are due to additional work on the part of the data analyst.
One of the promises of Splice-2 is to reduce the level of additional
work required of the analyst in such domains. We also find that a
state-of-the-art conceptual clustering method does not identify the
hidden context. |
| 9904 |
The Temporal Calculus of Conditional Objects and Conditional Events |
Jerzy Tyszkiewicz
Institute of Informatics
University of Warsaw
E-mail: jty@cse.unsw.edu.au
Arthur Ramer, Achim Hoffmann
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {ramer, achim}@cse.unsw.edu.au |
We consider the problem of defining conditional objects (a|b),
which would allow one to regard the conditional probability Pr(a|b)
as a probability of a well-defined event rather than as a shorthand
for Pr(ab)/\Pr(b). The next issue is to define boolean combinations
of conditional objects, and possibly also the operator of further
conditioning. These questions have been investigated at least since
the times of George Boole, leading to a number of formalisms proposed
for conditional objects, mostly of syntactical, proof-theoretic vein.
We propose a unifying, semantical approach, in which conditional
events are (projections of) Markov chains, definable in the three-valued
extension (TL}TL) of the past tense fragment of propositional linear
time logic (TL), or, equivalently, by three-valued counter-free Moore
machines. Thus our conditional objects are indeed stochastic processes,
one of the central notions of modern probability theory.
Our model precisely fulfills early ideas of de Finetti, and, moreover,
as we show in a separate paper, all the previously proposed algebras of
conditional events can be isomorphically embedded in our model. |
| 9903 |
Forced Simulation and Lock-Step Interface: A Formal Approach to
Automatic Component Matching |
Partha S. Roop, A. Sowmya
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {proop,sowmya}@cse.unsw.edu.au
S. Ramesh
Department of Computer Science and Engineering
Indian Institute of Technology
Bombay, India - 400 076
E-mail: ramesh@cse.iitb.ernet.in |
Component-based synthesis of embedded systems will lead to the reuse of
a vast library of hardware and software components and also facilitate
rapid prototyping. However it is still low key, a primary reason being the
lack of a systematic attempt at the development of automatic component
identification algorithms. The main task of such an algorithm is to
to map a design function to a device from a library of system-level
components. In this paper, we propose a novel notion of simulation called
forced simulation to formalize the correspondence between a function and
a device. What distinguishes forced simulation from other techniques is
the idea of forcing via an external interface, which can be automatically
synthesized, and is useful for adapting the system level component to
the given design functionality. We propose a new component matching
algorithm based on forced simulation and also propose a technique for
the automatic generation of the interface. Finally, a proof of soundness
of the approach is presented, based on reducing the synchronous parallel
composition of the interface and the device to Milner's weak bisimulation. |
| 9902 |
Data Spread: A Novel Authentication And Security Technique |
John Zic,
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: johnz@serg.cse.unsw.edu.au |
This paper describes an authentication and security protocol called
data spread for use on the Internet. The protocol applies address space
diversity to outgoing messages, and when combined with reasonable (but
not necessarily strong) encryption techniques, offers fast, secure and
authentic-able information exchange between communicating entities. |
| 9901 |
Forced Simulation: A Formal Approach to Component-Based Synthesis |
Partha S. Roop, A. Sowmya
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {proop,sowmya}@cse.unsw.edu.au
S. Ramesh
Department of Computer Science and Engineering
Indian Institute of Technology
Bombay, India - 400 076
E-mail: ramesh@cse.iitb.ernet.in |
Embedded systems are application-specific digital systems which are
normally designed using a microprocessor along with a set of programmable
hardware and software components. Component-based synthesis of these
systems will lead to the reuse of a vast library of hardware and
software components and also facilitate rapid prototyping. However
component based synthesis is still low key, a primary reason being the
lack of any systematic attempt at the development of automatic component
identification algorithms.
In [mitra96] an algorithm to map a design function to a device from a
library of system-level components was proposed. However, it was not based
on a formal setting and no proof of correctness was presented. In this
paper, we propose a novel notion of simulation called forced simulation
to formalize the correspondence between a function and a device. What
distinguishes forced simulation from other techniques is the idea of
forcing via an external interface, which can be automatically synthesized,
and is useful for adapting the system level component to the given design
functionality. We have proposed two different types of forced simulation
depending on the handling of internal events. |
| 9808 |
Statistical Properties of Simple Types |
Magorzata Moczurad, Marek Zaionc
Computer Science Department
Jagiellonian University
Nawojki 11, 30-072 Krakow, Poland
E-mail: {madry,zaionc}@softlab.ii.uj.edu.pl
Jerzy Tyszkiewicz
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
On leave from:
Institute of Informatics
University of Warsaw
Banacha 2, 02-097 Warszawa, Poland
E-mail: jty@mimuw.edu.pl |
We consider types and typed lambda calculus over a finite number of ground
types. We are going to investigate the size of the fraction of inhabited
types of the given length n against the number of all types of length n.
The plan of this paper is to find the limit of that fraction when $n
\impl \infty$. The answer to this question is equivalent to finding
the ``density'' of inhabited types in the set of all types, or the
so-called asymptotic probability of finding an inhabited type in the set
of all types. Under the Curry-Howard isomorphism this means finding the
density or asymptotic probability of provable intuitionistic propositional
formulas in the set of all formulas. For types with one ground type
(formulas with one propositional variable) we prove that the limit exists
and is equal to 1/2 + \sqrt{5}/10, which is approximately 72%. This means
that the random type (formula) of the large size is as likely as about 72%
to be inhabited (tautology). We also prove that for every finite number
k of ground-type variables, the density of inhabited types is always
positive and lies between (4k+1)/(2k+1)^2 and (3k+1)/(k+1)^2. Therefore
we can easily see that the density is decreasing to 0 with k going
to infinity. From the lower and upper bounds presented we can deduce
that at least 1/3 of classical tautologies are intuitionistic. |
| 9806 |
A General Architecture for Supervised Classification of
Multivariate Time Series |
Mohammed Waleed Kadous
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: waleed@cse.unsw.edu.au |
Supervised classification has been one of the most active areas of machine
learning research. However, the domains where it has been applied are
relatively limited. In particular, much of the work has focused on
classification in static domains, where the attributes of the training
examples are assumed not to change over time. In many domains, attributes
are not static; in fact, it is the way they vary temporally that can make
classification possible. Examples of such domains include speech
recognition, event recognition from sensors in robotics and analysis of
electrocardiographs.
So far, researchers tackling these domains have used ad-hoc techniques
for converting the problem to a standard classification task. This
fails to take into account both the special problems and special
heuristics applicable to temporal data.
This paper proposes a general architecture for classification of
multivariate time series. Training proceeds in five steps: extraction
of events from the data training based on parametrised event primitives;
clustering of the events in their parameter space to create synthetic
events; event attribution of the training data and finally building a
classifier with a conventional learner. Recognition takes two steps:
selective event searching for synthetic events within the test
instance (usually only a small subset of the synthetic events
generated in training need to be searched for), then feeding through
the classifier created in the training stage.
An example implementation of this general architecture is presented.
Some preliminary results of its application to recognition of signs
from Australian Sign Language are also discussed.
Keywords: machine learning, classification, temporal
classification, gesture recognition, time series. |
| 9804 |
Page Tables for 64-Bit Computer Systems |
Kevin Elphinstone, Gernot Heiser
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {kevine,gernot}@cse.unsw.edu.au
Jochen Liedtke
IBM TJ Watson Research Center
30 Saw Mill River Rd
Hawthorne NY, 10532, USA
E-mail: jochen@us.ibm.com |
Most modern wide-address computer architecture do not prescribe a page
table format, but instead feature a software-loaded TLB, which gives the
operating system complete flexibility in the implementation of page
tables. Such flexibility is necessary, as to date no single page table
format has been established to perform best under all loads. With the
recent trend to kernelised operating systems, which rely heavily on
mapping operations for fast data movement across address-spaces, demands
on page tables become more varied, and hence less easy to satisfy with a
single structure.
This paper examines the issue of page tables suitable for 64-bit
systems, particularly systems based on microkernels. We have implemented
a number of candidate page table structures in a fast microkernel and
have instrumented the kernel's TLB miss handlers. We have then measured
the kernel's performance under a variety of benchmarks, simulating loads
imposed by traditional compact address spaces (typical for UNIX systems)
as well as the sparse address spaces (typical for microkernel-based
systems). The results show that guarded page tables, together
with a software TLB cache, do not perform significantly worse than any
of the other structures, and clearly outperform the other structures
where the address space is used very sparsely. |
| 9801 |
L4 User Manual |
Alan Au, Gernot Heiser
Department of Computer Systems
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {alanau,gernot}@cse.unsw.edu.au |
This document is a user manual for the L4 micro-kernel. It gives an
introduction to the main concepts and features of L4, and explains
their use by a number of examples. The manual is generally platform
independent, however, examples are based on the C interface for
L4/MIPS. Actual system call C bindings and data formats differ
slightly on other platforms.
This document supplements, rather than replaces, the L4 Reference
Manual, and anyone intending to write an applications on top of L4
should obtain the L4 Reference Manual for their particular platform. |
| 9709 |
L4 Reference Manual --- MIPS R4x00, Version 1.0, Kernel Version 70 |
Kevin Elphinstone, Gernot Heiser
Department of Computer Systems
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
{kevine,gernot}@cse.unsw.edu.au
and
Jochen Liedtke
IBM T. J. Watson Research Center
30 Saw Mill River Road
Hawthorne, NY 10532, USA
jochen@watson.ibm.com |
This document describes the MIPS R4x00 implementation of the L4
microkernel. Specifically it describes Version 70 of the kernel, which
is the first version made available outside UNSW. The manual is based on
the L4/x86 reference manual Version 2.0 by Jochen Liedtke, and the
implementation is mostly compatible with that Intel version. Differences
and present implementation limitations are pointed out by
"implementation notes." |
| 9708 |
Extracting Hidden Context |
Michael Harries, Claude Sammut
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
Kim Horn
RMB Australia Limited
Level 5 Underwood House
37-47 Pitt Street
Sydney 2000 Australia
E-mail: mbh@cse.unsw.edu.au |
Concept drift due to hidden changes in context complicates learning
in many domains including financial prediction, medical diagnosis,
and network performance. Existing machine learning approaches to this
problem use an incremental learning, on-line paradigm. Batch, off-line
learners tend to be ineffective in domains with hidden changes in context
as they assume that the training set is homogeneous.
An off-line, meta-learning approach for the identification of hidden
context is presented. The new approach uses an existing batch learner
and the process of \emph{contextual} clustering to identify stable hidden
contexts and the associated context specific, locally stable concepts. The
approach is broadly applicable to the extraction of context reflected
in time and spacial attributes. Several algorithms for the approach are
presented and evaluated. A successful application of the approach to a
complex control task is also presented. |
| 9707 |
Performance Evaluation for Parallel Systems: A Survey |
Lei Hu and Ian Gorton
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {lei, iango}@cse.unsw.edu.au |
Performance is often a key factor in determining the success of a parallel
software system. Performance evaluation techniques can be classified into
three categories: measurement, analytical modeling, and simulation. Each
of them has several types. For example, measurement has software,
hardware, and hybrid; simulation has discrete event, trace/execution
driven, Monte Carlo; and analytical modeling has queueing network, Petri
net, etc.. This paper systematically reviews various techniques, and
surveys work done in each category. Also addressed and discussed are other
issues related to performance evaluation. These issues include how to
select metrics and proper techniques that are well suited for the
particular development stage, how to construct a good model, and how to
perform workload characterization. We also present fundamental laws and
scalability analysis techniques. While many techniques discussed are
common in both sequential and parallel system performance evaluation, our
focus is on the parallel systems. |
| 9705 |
Resource Management in the
Mungi Single-Address-Space Operating System |
Gernot Heiser, Fondy Lam, Stephen Russell
Department of Computer Systems
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: G.Heiser@unsw.edu.au |
We present the accounting system used for backing store management in
the Mungi single-address-space operating system. The model is designed
such that all accounting can be done asynchronously to operations on
storage objects, and hence without slowing down such operations. It is
based on bank accounts from which rent is collected for the storage
occupied by objects. Rent automatically increases as available storage
runs low, forcing users to release unneeded storage. Bank accounts
receive income, with a taxation system being used to prevent excessive
buildup of funds on underutilised accounts.
The accounting system is mostly implemented at user level, with minimal
support from the kernel. As a consequence, the accounting model can be
changed without modifying the Mungi kernel. |
| 9704 |
Implementation and Performance of the
Mungi Single-Address-Space Operating System |
Gernot Heiser, Kevin Elphinstone, Jerry Vochteloo, Stephen Russell
Department of Computer Systems
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
Jochen Liedtke
IBM T. J. Watson Research Center
30 Saw Mill River Road
Hawthorne, NY 10532, USA
E-mail: {gernot,jerry,kevine,smr}@cse.unsw.edu.au
jochen@watson.ibm.com |
Single-address-space operating systems (SASOS) are an attractive model
for making the best use of the wide address space provided by the latest
generations of microprocessors. SASOS remove the address space borders
which make data sharing between processes difficult and expensive in
traditional operating systems. This offers the potential of significant
performance advantages for applications where sharing is important, such
as object-oriented databases or persistent programming systems.
Previously published SASOS were not able to demonstrate these
performance advantages. We have built the Mungi system to show that these
advantages can indeed be realized. Mungi is a very ``pure'' SASOS,
featuring an unintrusive protection model based on sparse capabilities,
a fast protected procedure call mechanism, and uses virtual memory as
the exclusive inter-process communication mechanism, as well as for
I/O. We believe this simplicity of our model makes it easy to implement
it efficiently on conventional architectures.
Our realization of Mungi for the MIPS R4600 64-bit microprocessor is
presented, which is based on our implementation of the L4
microkernel. Mungi is shown to outperform a well-tuned commercial
operating system in several important aspects, such as task creation and
inter-process communications, and on the OO1 object-oriented database
benchmark. This demonstrates clearly that the SASOS concept is viable,
and that a well-designed microkernel is an excellent base on which to
build high-performance operating systems. |
| 9703 |
Estimator Variance in Reinforcement Learning: Theoretical Problems
and Practical Solutions |
Mark D. Pendrith and Malcolm R.K. Ryan
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {pendrith,malcolmr}@cse.unsw.edu.au |
In reinforcement learning, as in many on-line search techniques, a large
number of estimation parameters (e.g. Q-value estimates for 1-step Q-learning)
are maintained and dynamically updated as information comes to hand during the
learning process. Excessive variance of these estimators can be problematic,
resulting in uneven or unstable learning, or even making effective learning
impossible. Estimator variance is usually managed only indirectly, by
selecting global learning algorithm parameters (e.g. lambda for TD(lambda)
based methods) that are a compromise between an acceptable level of estimator
perturbation and other desirable system attributes, such as reduced estimator
bias. In this paper, we argue that this approach may not always be adequate,
particularly for noisy and non-Markovian domains, and present a direct
approach to managing estimator variance, the new ccBeta algorithm. Empirical
results in an autonomous robotics domain are also presented showing improved
performance using the ccBeta method. |
| 9702 |
An Analysis of non-Markov Automata Games: Implications for
Reinforcement Learning |
Mark D. Pendrith
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
and
Michael J. McGarity
School of Electrical Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {pendrith,mikem}@cse.unsw.edu.au |
It has previously been established that for Markov learning automata games,
the game equilibria are exactly the optimal strategies. In this paper,
we extend the game theoretic view of reinforcement learning to consider
the implications for ``group rationality'' in the more general situation
of learning when the the Markov property cannot be assumed. We show that
for a general class of non-Markov decision processes, if actual return
(Monte Carlo) credit assignment is used with undiscounted returns, we are
still guaranteed the optimal observation-based policies will be game
equilibria when using the standard ``direct'' reinforcement learning
approaches, but if either discounted rewards or a temporal differences
style of credit assignment method is used, this is not the case. |
| 9701 |
The Mungi Kernel API, Release 1.0 |
Gernot Heiser, Jerry Vochteloo, Kevin Elphinstone, Stephen Russell
Department of Computer Systems
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
E-mail: {gernot,jerry,kevine,smr}@cse.unsw.edu.au |
This document describes release 1.0 of the application programming
interface to the kernel of the Mungi single-address-space operating
system. This interface will, in general, only be used by low-level
software, most applications are expected to use a higher-level
interface implemented as system libraries. Such libraries will be
described in separate documents. |
| 9601 |
Supporting Persistent Object Systems in a Single Address Space |
Kevin Elphinstone, Stephen Russell and Gernot Heiser
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
and
Jochen Liedtke
German National Research Center for Information Technology
GMD SET-RS
Schlo{\ss} Birlinghoven
53757 Sankt Augustin
Germany
E-mail: {kevine,smr,gernot}@cse.unsw.edu.au
jochen.liedtke@gmd.de |
Single address space systems (SASOS) provide a programming model that is
well suited to supporting persistent object systems. In this paper we
show that stability can be implemented in the Mungi SASOS without
incurring overhead in excess of the inherent cost of shadow-paging. Our
approach is based on the introduction of aliasing into the SASOS model
and makes heavy use of user-level page fault handlers to allow
implementation outside the kernel. We also show how the demands of
database systems for control over page residency and physical I/O can be
accommodated. An approach to user-level implementation of distributed
shared memory (DSM) coherency models is outlined. |
| 9505 |
Simulation of Large-Area Silicon Solar Cells |
Gernot Heiser
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
and
Pietro P. Altermatt
Centre for Photovoltaic Systems and Devices
University of New South Wales
Sydney 2052 Australia
E-mail: G.Heiser@unsw.edu.au
pietro@vast.unsw.edu.au |
Two- and three-dimensional numerical modelling has recently become an
important tool for the characterisation and optimisation of
high-efficiency silicon solar cells. In the past, however, such
modelling could only be applied to small sections of the cells. While
such limited simulation domains are sufficient for the analysis of
bulk and surface properties, the analysis and optimisation of effects
like the losses resulting from the resistance of the metal contact
grid require a model of the full cell and need to include edge
effects. In this paper, we present an approach which combines
multi-dimensional device simulation with circuit simulation to produce
an accurate model of a full-sized high-efficiency solar cell. We
demonstrate the power of this approach by presenting the results of an
investigation of the series resistance of "passivated emitter, rear
locally diffused" (PERL) silicon solar cells. The insights gained in
that study triggered a small design change in the contact geometry,
which managed to reduce resistive losses by more than half and
contributed to a new efficiency world record. |
| 9504 |
Single Address Space Operating Systems |
Tim Wilkinson and Kevin Murray
Systems Architecture Research Centre
City University
Northampton Square
London EC1V 0HB, UK
and
Stephen Russell and Gernot Heiser
School of Computer Science and Engineering
University of New South Wales
Sydney 2052 Australia
and
Jochen Liedtke
German National Research Center for Information Technology
GMD SET-RS
Schlo{\ss} Birlinghoven
53757 Sankt Augustin
Germany
E-mail: {tim,kam\}@sarc.city.ac.uk
{smr,gernot\}@cse.unsw.edu.au
jochen.liedtke@gmd.de |
Single address-space operating systems offer many advantages for modern
systems design. We outline in this paper how such a system deals with
the issues of memory protection, user-level naming, resource management,
and translation management in a large, sparse address space, as well as
fault tolerance and reliability. We also explain how a POSIX compliant
interface can be supported on such a system. |
| 9503 |
Guarded Page Tables on the MIPS R4600 |
Jochen Liedtke
GMD - German National Research Center for Information Technology
GMD SET-RS, Shloss Birlinghoven
53757 Sankt Augustin, Germany
E-mail: jochen.lied@gmd.de
Kevin Elphinstone
School of Computer Science and Engineering
The University of New South Wales
Sydney 2052 Australia
E-mail: kevine@vast.unsw.edu.au
Date: 23 November 1995
Communicated by Jayasooriah |
The introduction of 64-bit microprocessors has increased demands
placed on virtual memory systems. The availability of large address
spaces has led to a flurry of new applications and operating systems
that further stress virtual memory systems. Consequently, much
interest has recently focussed on translation lookaside buffer (TLB)
performance and page table efficiency. Guarded Page Tables are a
mechanism for overcoming some of the problems associated with
conventional page tables.
Guarded Page Tables are tree structured like conventional page tables.
Also like conventional pages tables, they have the advantages of
supporting hierarchical operations and sharing of sub-trees. Unlike
conventional page tables, guarded page tables implement huge sparsely
occupied address spaces efficiently.
We describe guarded page tables and the associated parsing algorithm.
R4600 processor dependent micro-optimisation is undertaken and
presented. R4600 TLB refill is discussed in detail, including a
comparison of guarded page tables with more convention page tables. A
software second level TLB is introduced and analysed as a way of
increasing guarded page table performance. |
| 9502 |
Checkpointing and Recovery for Distributed Shared Memory Applications |
Jinson Ouyang and Gernot Heiser
Computer and Systems Technology Laboratory (CaST)
School of Computer Science and Engineering
The University of New South Wales
Sydney 2052 Australia
E-mail: jinsong,gernot@cse.unsw.edu.au |
This paper proposes an approach for adding fault
tolerance, based on consistent checkpointing, to distributed shared
memory applications. Two different mechanisms are presented to
efficiently address the issue of message losses due to either site
failures or unreliable non-FIFO channels. Both guarantee a correct and
efficient recovery from a consistent distributed system state following
a failure. A variant of the two-phase commit protocol is employed such
that the communication overhead required to take a consistent checkpoint
is the same as that of systems using a one-phase commit protocol,
while our protocol utilises stable storage more efficiently. A
consistent checkpoint is committed when the first phase of the protocol
finishes. |
| 9501 |
Medium Access Control for Synchronous Traffic in the AMNET LAN |
David Goodall
Computer and Systems Technology Laboratory (CaST)
School of Computer Science and Engineering
The University of New South Wales
Sydney 2052 Australia
and
Keith Burston
Manager, Communications Unit
The University of New South Wales
Sydney 2052 Australia
E-mail: castanets@vast.unsw.edu.au |
This report presents the medium access control (MAC) scheme designed for
supporting synchronous traffic within the AMNET LAN. Synchronous traffic is
supported directly at the MAC layer via a table mechanism, and is carried by
two different types of cell - synchronous cells, which carry data from a single
transmitter, and shared synchronous cells, which carry data from one or more
transmitters. The table mechanism provides guaranteed latency and bandwidth to
synchronous cell types. The latency involved in getting real-time data from a
source device to the LAN is minimised, thus simplifying devices and making
internetworking more feasible. This report is intended to describe the
different synchronous cell types, the table mechanism, and algorithms for
allocation of bandwidth using the table. |
| 9413 |
A Simple, Expressive Real-Time CCS |
C. Fidge
Software Verification Research Centre,
Department of Computer Science,
The University of Queensland, Queensland 4072,
Australia.
E-mail: cjf@cs.uq.oz.au
J. Zic
Software Engineering Research Group,
School of Computer Science and Engineering,
University of New South Wales, NSW 2052,
Australia.
E-mail: John.Zic@serg.cse.unsw.edu.au |
We describe a new `real-time' process algebra with simple semantics but
considerable expressive power. It exhibits the advantages of both the
`constraint-oriented' and `marker variable' specification styles. The
definition extends Milner's CCS, firstly with a simple notion of
absolute time added to actions, and then with relative timing
expressions which may refer to time markers. |
| 9412 |
Representing Closed CCS Systems by Petri Nets |
Jacek Olszewski
Address: Microsoft Institute of Advanced Software Technology
65 Epping Rd, North Ryde, 2113 Australia
(on leave from SCSE, UNSW)
E-mail:jacek@cse.unsw.edu.au |
This paper describes and proves a simple transformation of CCS compositions
into Petri nets. Under certain conditions, additional to the CCS syntax rules,
the resulting Petri nets are finite, and firing of their transitions
corresponds to handshakes in CCS compositions. Such correspondence also holds
between simultaneous firing of several transitions and multiple handshakes. The
transformation has proved useful in a fast deadlock detection tool developed
for CCS specifications. |
| 9411 |
Issues in Implementing Virtual Memory |
Kevin Elphinstone, Stephen Russell and Gernot Heiser
School of Computer Science and Engineering
The University of NSW
Sydney 2052 Australia
E-mail: kevine@vast.unsw.edu.au
Date: 29 SEPTEMBER 1994 |
Several factors are rapidly increasing the demands being placed on
virtual memory implementations. Large address spaces, increasing
sparseness, and novel operating systems are not well supported by
traditional tree-based page tables. New approaches are needed to
overcome these problems.
This paper examines the advantages and disadvantages of conventional
virtual address translation schemes. It then describes the performance
costs caused by recent changes in hardware and operating system
architectures. While there is much active research directed towards
reducing these costs, it is mostly intended to provide better support
for Unix style systems. Many issues are still unresolved, particularly
those relating to the support of the large, sparse address spaces used
by single address space operating systems. |
| 9410 |
On Reinforcement Learning of Control Actions in Noisy
and Non-Markovian Domains. |
Mark Pendrith
School of Computer Science and Engineering
The University of New South Wales
Sydney 2052 Australia
E-mail: pendrith@cse.unsw.edu.au
Date: 30 August 1994
Communicated by Claude Sammut |
If reinforcement learning (RL) techniques are to be used for ``real world''
dynamic system control, the problems of noise and plant disturbance will have
to be addressed. This study investigates the effects of noise/disturbance on
five different RL algorithms: Watkins' Q-Learning (QL); Barto, Sutton and
Anderson's Adaptive Heuristic Critic (AHC); Sammut and Law's modern variant
of Michie and Chamber's BOXES algorithm; and two new algorithms developed
during the course of this study. Both these new algorithms are conceptually
related to QL; both algorithms, called P-Trace and Q-Trace respectively,
provide for substantially faster learning than straight QL overall, and for
dramatically faster learning (by up to a factor of 200) in the special case
of learning in a noisy environment for the dynamic system studied here
(a pole-and-cart simulation).
As well as speeding learning, both the P-Trace and Q-Trace algorithms have
been designed to preserve the ``convergence with probability 1'' formal
properties of standard QL, i.e. that they be provably ``correct'' algorithms
for Markovian domains for the same conditions that QL is guaranteed to be
correct. We present both arguments and experimental evidence that ``trace''
methods may prove to be both faster and more powerful in general
than TD (Temporal Difference) methods. The potential performance improvements
using trace over pure TD methods may turn out to be particularly important
when learning is to occur in noisy or stochastic environments, and in the case
where the domain is not well-modelled by Markovian processes.
A surprising result to emerge from this study is evidence for hitherto
unsuspected chaotic behaviour with respect to learning rates exhibited by the
well-studied AHC algorithm. The effect becomes more pronounced as noise
increases. |
| 9409 |
Tracing Kernel Activity in SunOS 4.0 |
David Goodall and Stephen Russell |
This paper describes a software tool for tracing kernel activity
within the SunOS 4.0 operating system. The tool is designed as a
pseudo-controller with separate pseudo-devices to capture event
streams from various parts of the operating system. A high resolution
interval timer is attached to the target system's SCSI port in order
to provide hardware support for timestamps. Use of the timer also
allows measurement of CPU usage by the instrumentation system.
E-mail: disy@vast.unsw.edu.au |
| 9407 |
Time Constrained Buffer Specifications in CSP+T and Timed CSP |
John J. Zic |
A finite buffer with time constraints on the rate of accepting inputs,
producing outputs and message latency is specified using both Timed CSP
and a new real-time specification language, CSP+T. CSP+T adds
expressive power to some of the sequential aspects of CSP and allows
the description of complex event timings from within a single
sequential process. On the other hand, Timed CSP encourages event
timing descriptions to be built up in a constraint-oriented manner with
the parallel composition of several processes. Although these represent
two complementary specification styles, both provide valuable insights
into specification of complex event timings.
E-mail: johnz@cse.unsw.edu.au |
| 9406 |
A Parallel Approach to High-Speed Protocol Processing |
Toong Shoon Chan and Ian Gorton |
A rapid increase in the transmission bandwidth of optical networks has
created a bottleneck in protocol processing at the end systems. This
has resulted in the inability of applications and network protocols to
exploit the full bandwidth of a high-speed network. This paper presents
a parallel architecture that is designed to support high-speed protocol
processing. The advent of the T9000 transputer and C104 router
technology has provided a platform that is suitable for the
construction of a highly parallel and scalable protocol processing
architecture based on packet and functional parallelism. A simulation
of the architecture has been implemented and has demonstrated the
advantage of exploiting a parallel architecture for protocol
processing.
Email: chants, iango@spectrum.cs.unsw.oz.au |
| 9405 |
On Aggregating Teams of Learning Machines |
Sanjay Jain and Arun Sharma |
The present paper studies the problem of when a team of learning
machines can be aggregated into a single learning machine without any
loss in learning power. The main results concern aggregation ratios for
vacillatory identification of languages from texts. For a positive
integer n, a machine is said to TxtFex_n-identify a language L just in
case the machine converges to up to n grammars for L on any text for L.
For such identification criteria, the aggregation ratio is derived for
the n=2 case. It is shown that the collection of languages that can be
TxtFex_2 identified by teams with success ratio greater than 5/6 are
the same as those collections of languages that can be
TxtFex_2-identified by a single machine. It is also established that
5/6 is indeed the cut-off point by showing that there are collections
of languages that can be TxtFex_2-identified by a team employing 6
machines, at least 5 of which are required to be successful, but cannot
be TxtFex_2-identified by any single machine. Additionally,
aggregation ratios are also derived for finite identification of
languages from positive data and for numerous criteria involving
language learning from both positive and negative data.
Email: arun@cse.unsw.edu.au |
| 9404 |
On the Intrinsic Complexity of Language Identification |
Sanjay Jain and Arun Sharma |
A new investigation of the complexity of language identification is
undertaken using the notion of reduction from recursion theory and
complexity theory. The approach, referred to as the intrinsic
complexity of language identification, employs notions of `weak' and
`strong' reduction between learnable classes of languages. The
intrinsic complexity of several classes are considered and the results
agree with the intuitive difficulty of learning these classes. Several
complete classes are shown for both the reductions and it is also
established that the weak and strong reductions are distinct.
An interesting result is that the self referential class of Wiehagen
in which the minimal element of every language is a grammar for the
language and the class of pattern languages introduced by Angluin are
equivalent in the strong sense.
This study has been influenced by a similar treatment of function
identification by Freivalds, Kinber, and Smith.
Email: arun@cse.unsw.edu.au |
| 9403 |
Motion planning in Prototypical Corridors |
N. Ahmed and A. Sowmya |
We discuss the motion planning of a rectangular moving object in
certain prototypical situations arising in a 2-D isothetic workspace.
We have suggested three possible motion strategies involving rotation
and translation of the moving object negotiating an L-shaped
corridor. We have also given simulation results to compare the three
cases of the proposed motion.
E-mail: sowmya@cse.unsw.edu.au
First author's affiliation:
Department of Computer Science
James Cook University of North Queensland
Townsville QLD 4811, Australia ) |
| 9402 |
HTPNET: A New Transport Protocol for High-speed Networks |
Toong Shoon Chan and Ian Gorton |
The quantum increase in transmission speed of optical fibre networks has
created a bottleneck in transport protocol processing at host systems. In
this paper we present a new transport protocol system, HTPNET, that is
designed to overcome this protocol processing bottleneck. HTPNET is based
on a highly parallel architecture and is designed to exploit the evolving
characteristics of high-speed networks. HTPNET uses an out-of-band signalling
system based upon transmitter-paced periodic exchanges of state information
between end systems. This mechanism exhibits several attractive properties
which have been demonstrated to perform efficiently in a high-speed
environment with high-bandwidth-delay-product. A prototype implementation
of HTPNET has been constructed from a network of T800 transputers. The results
obtained from this implementation are presented: these demonstrate the
advantages of exploiting a parallel architecture for protocol processing. |
| 9401 |
Extending Statecharts with Temporal Logic |
A. Sowmya and S. Ramesh |
Statecharts is a behavioural specification language for the
specification of real-time event driven reactive systems. Recently,
statecharts was related to a logical specification language, using
which safety and liveness properties could be expressed; this language
provides a compositional proof system for statecharts. However, the
logical specification language is flat, with no facilities to account
for the structure of statecharts; further, the primitives of this
language are dependent on statecharts syntax, and cannot be related
directly to the problem domain. This paper discusses a temporal
logic-based specification language called FNLOG which addresses these
problems. |
| 9318 |
Designing a Video Rate Edge Detection ASIC |
Mehdi N. Fesharaki and Graham R. Hellestrand |
A method of generating a video rate edge maps, and thereby segmenting
an image into regions based on the Kolmogorov-Smirnov test is
presented. By applying this test and comparing cumulative distribution
functions of the intensities in the neighbourhood of a given pixel, the
pixel can be accurately classified as either an edge pixel on the
boundary between regions, or as a pixel belonging to a particular type
of region. It is shown that a custom VLSI design for this algorithm
using parallel pipelined architecture is realisable. The outline of
this design is presented and then the critical path modules are
simulated. |
| 9317 |
Non-Interleaving Semantics for CCS and Fast Deadlock Detection |
Jacek Olszewski |
This paper proposes a non-interleaving semantics for CCS, and defines a
class of CCS compositions for which interleaving and non-interleaving
semantics are equivalent. It also presents a fast software tool for
analysis of CCS compositions under non-interleaving semantics. The tool
employs Petri net techniques with multiple transition firings. |
| 9316 |
Real-Time Colour Image Segmentation |
Mehdi N. Fesharaki and Graham R. Hellestrand |
This paper describes a new method for colour image segmentation. The
algorithm is based on testing the homogeneity of pixels around a center
pixel by using statistical inference techniques. A 5 by 5 window around
each pixel is partitioned into two sub-samples in different
orientations. Then the cumulative distribution function of two
sub-samples are compared with each other. Based on the
Kolmogorov-Smirnov statistic, the homogeneity of two sub-samples is
verified. If all pixels within the window are homogeneous, therefore,
the computed statistic for all different partitionings must verify the
homogeneity; otherwise, the homogeneity is rejected. As well, the
computed statistic is combined with the intensity uniformity of two
adjacent pixels to prevent oversegmented and/or undersegmented results.
Moreover, we consider how the algorithms can be effectively implemented
as a real-time hardware design. |
| 9315 |
Two-dimensional Numerical Simulations of High-efficiency Silicon Solar Cells
(The text of this report will also appear in the Microelectronics Journal) |
Gernot Heiser, Armin G. Aberle, Stuart R. Wenham, Martin A. Green |
This paper reports on the first use of two-dimensional (2D) device
simulation for optimising the front-finger spacing of one-sun
high-efficiency silicon solar cells of practical dimensions. We
examine the 2D current flow patterns in these devices under various
illumination conditions, resulting in improved insight into the
operating conditions of the cells. Results for the optimal spacing of
the front metal fingers are presented and compared to predictions
obtained from 1D simulations. We also address difficulties facing the
numerical modelling of high-efficiency silicon solar cells. |
| 9314 |
Mungi: A Distributed Single Address-Space Operating System
(The text of this report has been acepted for ACSC-17) |
Gernot Heiser, Kevin Elphinstone, Stephen Russell, Jerry Vochteloo |
With the development of 64-bit microprocessors, it is now possible to
combine local, secondary and remote storage into a large single
address-space. This results in a uniform method for naming and accessing
objects regardless of their location, removes the distinction between
persistent and transient data, and simplifies the migration of data and
processes.
This paper describes the Mungi single address-space operating
system. Mungi provides a distributed single level address-space, which
is protected using password capabilities. The protection system performs
efficiently on conventional architectures, and is simple enough that
most programs do not need to be aware of its operation. |
| 9312 |
Address Space Management Issues in the Mungi Operating System |
Kevin Elphinstone |
The Mungi operating system features a single 64 bit persistent address
space encompassing all data in the system. This differs dramatically
from current generation operating systems in which each process has
its own address space and persistent data is stored in a filesystem.
This report is a preliminary investigation of address space management
issues raised by adopting a single persistent address space model.
Issues examined are internal and external fragmentation of the address
space, reuse versus no-reuse allocation policies, and page table
structures used to support the address space. |
| 9311 |
Conceptual Graphs for Natural Language Representation |
Graham A. Mann |
Conceptual graphs are abstract data structures that can form the basis
of a knowledge representation system. Since their introduction by Sowa
in 1984, they have formed the core of a flourishing research effort,
with applications in databases and artificial intelligence. The basics
of conceptual graph theory are outlined, including the organisation of
existential, finite, bipartite directed graphs and their relationship
to first order predicate logic. A definition of the basic functions
defined over such graphs follows, including the canonical formation
rules and some higher order functions intended to support reasoning.
With carefully designed semantic knowledge in the form of catalogues of
concepts and relations, a conceptual graph processing system can
support knowledge representation. A new evaluation of the strengths and
weaknesses of conceptual graphs with respect to a theoretical view of
knowledge representation which enumerates five roles which the
representation must play: provision of a theory of intelligent
reasoning, ontological commitment, object surrogacy, provision of a
practical computing medium, and human read/writeability, is made.
Finally, existing methods of using the conceptual graphs for natural
language comprehension are discussed, and a new theory of conceptual
assembly is proposed. Access to an experimental conceptual graph
processor written in Common Lisp is offered in an Appendix A. |
| 9309 |
Using CSP+T to Describe a Timing Constrained Stop-and-Wait Protocol |
John J. Zic |
This paper presents a novel description of a time-constrained stop and wait
protocol using an extended CSP model. The timing constraints examined
include the usual message transit delay, as well as message input rate
limitations and message timeouts.
The extended CSP model used for this example is based on associating finite
time intervals with each event the process engages. These time intervals in
turn are functions over a set of markers events. |
| 9308 |
A Comparison of Two Real-time Description Techniques |
John J. Zic |
A new real-time description language based on Hoare's CSP is proposed,
and compared to the more usual Timed CSP in its effectiveness in describing
a buffer with differing input and output rates and transit delay requirements.
It is found that the new notation offers a concise, natural way of formulating
complex timing relationships. |
| 9306 |
VHDL vs Functional Hardware Description: A Comparison and Critique |
P. Kanthamanon, G. R. Hellestrand and M. C. Kam |
This paper presents a comparison of two Hardware Description Languages (HDL)-
VHDL and MODAL which employ different description styles for hardware
specification. The comparison is both qualitative and quantitative and based
on examples written in both languages. The languages are distinct in their
power to describe hardware at various levels of abstraction. The results show
that the functional description style, as used in MODAL, provides a more
accurate description of hardware and modelling of hardware timing without loss
of behavioural descriptive power. |
| 9305 |
Signal Transition Graph Constraints for Synthesis of Hazard-Free
Asynchronous Circuits with Unbounded-Gate Delays |
Radhakrishna Nagalla and Graham Hellestrand |
A synthesis procedure for asynchronous control circuits from a high level
specification, signal transition graph (STG), is described. In this paper,
we propose some syntactic constraints on STG to guarantee hazard-free
implementation. We have introduced a global persistency concept in order to
establish the relationship between the persistency concept introduced by Chu
[2] (which we call local persistency) and the consistent state coding (CSC).
The STG syntactic constraints required to compute the "input set" of a signal
are identified. We analyze all hazards under both single and multiple input
change conditions and propose necessary changes to the net contraction and
logic synthesis procedures. The proposed changes are guaranteed to generate
hazard-free circuits with the unbounded-gate delay model, if the STG is live,
safe and has consistent state coding. |
| 9304 |
Marksheets: marking easier and more consistently |
J. Lions |
This report introduces formally the idea of marksheets as an aid for
examination marking. A marksheet is an A4 sheet of paper that has been
specially prepared to aid the recording of mark gained by one student during
an examination.
Marking is a difficult and stressful process that involves understanding and
interpreting the sometimes tangled outpourings and associated thought
processes of students under examination. Straight-forward approaches that
suffice for small classes may no longer do so as class sizes grow.
The object of preliminary marking is to validate and extend the marking
scheme, and to ensure that all ways of answering each question have been
discovered, considered and calibrated. In general, the marksheet changes
whenever a new style of answer, or new variation is discovered. During the
cycle of review and re-assessment, the marksheet goes through several
iterations.
When the time for final marking arrives, each script is assessed
independently and all marks, comments and notes about the script are recorded
on one single copy of the marksheet.
The preparation of a marksheet may take considerable time and effort.
Marksheets cater to a need that did not exist only a few years ago, and their
production is facilitated by technology that also did not exist a few years
ago. |
| 9303 |
Capability-Based Protection in a Persistent Global Virtual Memory System |
Jerry Vochteloo, Stephen Russell, Gernot Heiser |
A single address-space encompassing all virtual memory of a distributed
computer system is an ideal environment for a persistent system. The
issue of providing effective and efficient protection of objects in such
an environment has, however, not been addressed satisfactorily. We
propose a system which is based on password capabilities. A
system-maintained data structure called the {\em capability tree} is
used for long-term storage of capabilities, and reflects the
hierarchical structure of object privacy. A second system data
structure, the {\em active protection domain}, allows the system to
find capabilities quickly when validating memory accesses. The proposal
supports inheritance of protection domains, as well as temporary
extension of protection domains to support privileged procedures.
Untrusted programs can be confined to run in a restricted protection
domain. The protection system performs efficiently on conventional
architectures, and is simple enough that most programs do not need to be
aware of its operation. |
| 9302 |
A Distributed Single Address-Space Operating System Supporting Persistence |
Gernot Heiser, Kevin Elphinstone, Stephen Russell, Graham R. Hellestrand |
Persistence has long been difficult to integrate into operating systems.
The main problem is that pointers lose their meaning once they are taken
out of their address-space. We present a distributed system which has a
single address-space encompassing all virtual memory of every node in
the system. This design has become possible (and practicable) with the
advent of 64-bit microprocessors.
In our system, every pointer retains its meaning independent of its
location, even across nodes or on secondary storage. No restrictions are
imposed on the use of pointers by application programs. Hence
persistence is naturally and elegantly integrated into the system.
Further features are uniform addressing and unlimited sharing of data,
and memory protection based on password capabilities, making the system
easy to use. A reliable paging protocol ensures that the impact of node
crashes on other parts of the system is minimised. |
| 9301 |
Computational Limits on Team Identification of Languages |
Sanjay Jain and Arun Sharma |
A team of learning machines is essentially a multiset of learning
machines. A team is said to successfully identify a concept just
in case each member of some nonempty subset of the team identifies
the concept. Team identification of programs for computable
functions from their graphs has been investigated by Smith. Pitt
showed that this notion is essentially equivalent to function
identification by a single probabilistic machine.
The present paper introduces, motivates, and studies the more
difficult subject of team identification of grammars for languages
from positive data. It is shown that an analog of Pitt's result
about equivalence of team function identification and probabilistic
function identification does not hold for language identification,
and the results in the present paper reveal a very complex
structure for team language identification. It is also shown that
for certain cases probabilistic language identification is strictly
more powerful than team language identification.
Proofs of many results in the present paper involve very
sophisticated diagonalization arguments. Two very general tools are
presented that yield proofs of new results from simple arithmetic
manipulation of the parameters of known ones. |
| |
|
