UNSW Faculty of Engineering PRINT VERSION SITE MAP  
cse | School of Computer Science and Engineering (CRICOS Provider No. 00098G)
    #About CSE     #Undergraduate Study     #Postgraduate Study     #Timetables & Courses     #Research & Publications     #People & Work Units     #Help & Resources     #News & Events     #High School Portal
    #Welcome     <h3><h3>#</h3></h3>Research Study     #Research Areas     #Research Groups     #Research Centres     #Seminars     #Publications

Last updated 14.06.06

[Link to the main School page]


UNSW Computer Science and Engineering Technical Reports

The links in the index below lead first to an abstract and then to pdf file of the technical report. These reports are also available by anonymous ftp from ftp.cse.unsw.edu.au:pub/users/reports/papers.

2004 Technical Reports

2003 Technical Reports

2002 Technical Reports

2001 Technical Reports

2000 Technical Reports

1999 Technical Reports

1998 Technical Reports

1997 Technical Reports

1996 Technical Reports

1995 Technical Reports

1994 Technical Reports

1993 Technical Reports

Technical Report UNSW-CSE-TR-0001

TITLE: Measure for Vector Approximation

AUTHOR(S): Benjamin Briedis

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0001.pdf

Technical Report UNSW-CSE-TR-0003

TITLE: The Logical Validation of Mathematical Diagrammatic Proofs

AUTHOR(S): Christina L. Jenkin

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0003.pdf

Technical Report UNSW-CSE-TR-0004

TITLE: A Formal Approach to Component Based Development of Embedded Systems

AUTHOR(S): Partha S. Roop, A. Sowmya

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0004.pdf

Technical Report UNSW-CSE-TR-0005

TITLE: Specifications for End to End IP Rate Control (Version 1.0)

AUTHOR(S): Abdul Aziz Mustafa, Mahbub Hassan and Sanjay Jha

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0005.pdf

Technical Report UNSW-CSE-TR-0006

TITLE: EPDL: A Logic for Causal Reasoning

AUTHOR(S): Dongmo Zhang and Norman Foo

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0006.pdf

Technical Report UNSW-CSE-TR-0007

TITLE: Jigsaw: the unsupervised construction of spatial representations

AUTHOR(S): Mark W. Peters and Barry Drake

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0007.pdf

Technical Report UNSW-CSE-TR-0101

TITLE: CVSSearch: Searching through Source Code using CVS Comments

AUTHOR(S): Annie Chen, Eric Chou, Joshua Wong, Andrew Y. Yao, Qing Zhang, School of Computer Science and Engineering,

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0101.pdf

Technical Report UNSW-CSE-TR-0103

TITLE: A Component Architecture for System Extensibility

AUTHOR(S): Antony Edwards and Gernot Heiser School of Computer Science and Engineering,

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0103.pdf

Technical Report UNSW-CSE-TR-0104

TITLE: L4 Reference Manual --- Alpha 21x64

AUTHOR(S): Daniel Potts, Simon Winwood and Gernot Heiser School of Computer Science and Engineering,

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0104.pdf

Technical Report UNSW-CSE-TR-0105

TITLE: A Platform for Portable and Embedded Systems Research

AUTHOR(S): Adam Wiggins

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0105.pdf

Technical Report UNSW-CSE-TR-0106

TITLE: Code Search based on CVS Comments: A Preliminary Evaluation

AUTHOR(S): Annie Chen, Yun Ki Lee, Andrew Y. Yao, Amir Michail School of Computer Science and Engineering,

ABSTRACT

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). ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0106.pdf

Technical Report UNSW-CSE-TR-0107

TITLE: Analysing Cache Memory Behaviour for Programs with IF Statements

AUTHOR(S): Xavier Vera and Jingling Xue

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0107.pdf

Technical Report UNSW-CSE-TR-0108

TITLE: Self-Coordinated and Self-Traced Composite Services with Dynamic Provider Selection

AUTHOR(S): B. Benatallah(*), M. Dumas(**), M.-C. Fauvet(*) and H. Paik(*) (*) School of Computer Science and Engineering (**) Cooperative Information Systems Research Centre

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0108.pdf

Technical Report UNSW-CSE-TR-0109

TITLE: Let's Study Whole-Program Cache Behaviour Analytically

AUTHOR(S): Xavier Vera and Jingling Xue Jingling Xue

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0109.pdf

Technical Report UNSW-CSE-TR-0110

TITLE: A Dynamically-Balanced Walking Biped

AUTHOR(S): Graham Mann*, Bruce Armstrong*, Phil Preston**, Barry Drake** * School of Information Technology

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0110.pdf

Technical Report UNSW-CSE-TR-0111

TITLE: Towards Patterns of Web Services Composition

AUTHOR(S):

ABSTRACT

Abstract 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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0111.pdf

Technical Report UNSW-CSE-TR-0112

TITLE: An Efficient IP Matching Tool using Forced Simulation

AUTHOR(S): Partha Roop A. Sowmya S. Ramesh Haifeng Guo

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0112.pdf

Technical Report UNSW-CSE-TR-0201

TITLE: Design and Implementation of the L4 Microkernel for Alpha Multiprocessors

AUTHOR(S): Daniel Potts, Simon Winwood, Gernot Heiser

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0201.pdf

Technical Report UNSW-CSE-TR-0202

TITLE: Avoiding Useless Packet Transmission for Multimedia over IP Networks: The Case of Single Congested Link

AUTHOR(S): Jim Wu and Mahbub Hassan

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0202.pdf

Technical Report UNSW-CSE-TR-0203

TITLE: The Responsive Bisimulations in the polar \pi-calculus

AUTHOR(S): Xiaogang Zhang and John Potter

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0203.pdf

Technical Report UNSW-CSE-TR-0204

TITLE: A Constraint Description Calculus for Compositional Concurrent Objects

AUTHOR(S): Xiaogang Zhang and John Potter

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0204.pdf

Technical Report UNSW-CSE-TR-0205

TITLE: The Responsive Bisimulations in the \kappa-calculus

AUTHOR(S): Xiaogang Zhang and John Potter

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0205.pdf

Technical Report UNSW-CSE-TR-0206

TITLE: Title : The Survey of Bandwidth Broker

AUTHOR(S): Shaleeza Sohail and Sanjay Jha

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0206.pdf

Technical Report UNSW-CSE-TR-0207

TITLE: Active Protocol Label Switching (APLS)

AUTHOR(S): William Lau and Sanjay Jha

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0207.pdf

Technical Report UNSW-CSE-TR-0208

TITLE: Design and Implementation of a Virtual Quality of Service MAC Layer (VQML) for Wireless LANs

AUTHOR(S):

ABSTRACT

Abstract 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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0208.pdf

Technical Report UNSW-CSE-TR-0209

TITLE: A Fast and Versatile Path Index for Querying Semi-Structured Data

AUTHOR(S): Michael Barg

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0209.pdf

Technical Report UNSW-CSE-TR-0210

TITLE: A Theory of Compositional Concurrent Objects

AUTHOR(S): Xiaogang Zhang and John Potter

ABSTRACT

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 ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0210.pdf

Technical Report UNSW-CSE-TR-0213

TITLE: SCCircal: a Static Compiler Mapping XCircal to Virtex FPGAs

AUTHOR(S): J\'er\'emie Detrey Oliver Diessel

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0213.pdf

Technical Report UNSW-CSE-TR-0214

TITLE: A Constructive Proof of the Turing Completeness of Circal

AUTHOR(S): J\'er\'emie Detrey Oliver Diessel

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0214.pdf

Technical Report UNSW-CSE-TR-0215

TITLE: Avoiding Useless Packet Transmission for Multimedia over IP Networks: The Case of Multiple Congested Links

AUTHOR(S): Jim Wu and Mahbub Hassan

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0215.pdf

Technical Report UNSW-CSE-TR-0216

TITLE: Avoiding Useless Packet Transmission for Multimedia over IP Networks: The Case of Multiple Multimedia Flows

AUTHOR(S): Jim Wu and Mahbub Hassan

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0216.pdf

Technical Report UNSW-CSE-TR-0301

TITLE: Parallelized FTP

AUTHOR(S): Shaleeza Sohail, Sanjay Jha and Hossam ElGindy

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0301.pdf

Technical Report UNSW-CSE-TR-0302

TITLE: Invented Predicates to Reduce Knowledge Acquisition Effort

AUTHOR(S): Hendra Suryanto and Paul Compton Artificial Intelligence Department

ABSTRACT

Abstract 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%. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0302.pdf

Technical Report UNSW-CSE-TR-0303

TITLE: Towards Unstrusted Device Drivers

AUTHOR(S): Ben Leslie, Gernot Heiser

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0303.pdf

Technical Report UNSW-CSE-TR-0304

TITLE: A Formal Approach to Interface Synthesis for SoC Design

AUTHOR(S): Vijay D'silva

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0304.pdf

Technical Report UNSW-CSE-TR-0305

TITLE: An Efficient Resource Management Framework for Programmable and Active Networks.

AUTHOR(S): Fariza Sabrina and Sanjay Jha

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0305.pdf

Technical Report UNSW-CSE-TR-0306

TITLE: Design and Performance analysis of CBCSWFQ packet scheduling algorithm.

AUTHOR(S): Fariza Sabrina and Sanjay Jha

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0306.pdf

Technical Report UNSW-CSE-TR-0307

TITLE: Itanium Page Tables and TLB

AUTHOR(S): Matthew Chapman, Ian Wienand, Gernot Heiser

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0307.pdf

Technical Report UNSW-CSE-TR-0308

TITLE: Safe State Abstraction and Discounting in Hierarchical Reinforcement Learning

AUTHOR(S): Bernhard Hengst

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0308.pdf

Technical Report UNSW-CSE-TR-0309

TITLE: "Variable Resolution Hierarchical RL"

AUTHOR(S): Bernhard Hengst

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0309.pdf

Technical Report UNSW-CSE-TR-0310

TITLE: Update Synchronization for Mobile XML Data

AUTHOR(S): Franky Lam, Nicole Lam, Raymond K. Wong

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0310.pdf

Technical Report UNSW-CSE-TR-0311

TITLE: An Efficient WordNet-Based Summarizer for Large Text Documents

AUTHOR(S): Raymond K. Wong, Chit Sia

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0311.pdf

Technical Report UNSW-CSE-TR-0312

TITLE: Efficient Query Relaxation for Semistructured Data

AUTHOR(S): Michael Barg, Raymond K. Wong

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0312.pdf

Technical Report UNSW-CSE-TR-0313

TITLE: On Structural Inference for XML Data

AUTHOR(S): Raymond K. Wong, Jason Sankey

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0313.pdf

Technical Report UNSW-CSE-TR-0314

TITLE: Adaptive Change Management for Semi-structured Data

AUTHOR(S): Raymond K. Wong, Nicole Lam

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0314.pdf

Technical Report UNSW-CSE-TR-0315

TITLE: On Clustering Schemes for XML Databases

AUTHOR(S): Damien K. Fisher, William M. Shui, Franky Lam, Raymond K. Wong

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0315.pdf

Technical Report UNSW-CSE-TR-0316

TITLE: Efficient Ordering for XML Data

AUTHOR(S): Damien K. Fisher, Franky Lam, William M. Shui, Raymond K. Wong

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0316.pdf

Technical Report UNSW-CSE-TR-0317

TITLE: Fast Ordering for Changing XML Data

AUTHOR(S): Damien K. Fisher, Franky Lam, William M. Shui, Raymond K. Wong

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0317.pdf

Technical Report UNSW-CSE-TR-0318

TITLE: Intertac Software Architecture

AUTHOR(S): Cat Kutay

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0318.pdf

Technical Report UNSW-CSE-TR-0319

TITLE: Peering and Querying e-Catalog Communities

AUTHOR(S): Boualem Benatallah (1), Mohand-Said Hacid (2), Hye-young Paik (1) (1) CSE, University of New South Wales, Australia,

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0319.pdf

Technical Report UNSW-CSE-TR-0320

TITLE: Skipping Strategies for Efficient Structural Joins

AUTHOR(S): Franky Lam, William M. Shui, Damien K. Fisher, Raymond K. Wong

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0320.pdf

Technical Report UNSW-CSE-TR-0321

TITLE: A Survey on the Interaction Between Caching, Translation and Protection

AUTHOR(S): Adam Wiggins

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0321.pdf

Technical Report UNSW-CSE-TR-0322

TITLE: A Theory of Proximity Relations

AUTHOR(S): Jane Brennan, Eric Martin

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0322.pdf

Technical Report UNSW-CSE-TR-0323

TITLE: Failure-Oriented Path Restoration Algorithm for Survivable Networks

AUTHOR(S): William Lau and Sanjay Jha

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0323.pdf

Technical Report UNSW-CSE-TR-0325

TITLE: Automated Interface Synthesis

AUTHOR(S): Vijay D'Silva, Arcot Sowmya S. Ramesh (permanent)

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0325.pdf

Technical Report UNSW-CSE-TR-0328

TITLE: State Transition Model to Characterize TCP Window Control Behavior in Wired/Wireless Internetworks

AUTHOR(S): Debashis Saha Sanjay K Jha

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0328.pdf

Technical Report UNSW-CSE-TR-0331

TITLE: An Anycast Service for Hybrid Sensor/Actuator Networks

AUTHOR(S): Wen Hu

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0331.pdf

Technical Report UNSW-CSE-TR-0335

TITLE: Planning an Empirical Experiment To Evaluate The Effects Of Pair Work On The Design Phase Of The Software Lifecycle

AUTHOR(S): H. Al-Kilidar, R. Jeffery, C. Kutay A. Aurum

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0335.pdf

Technical Report UNSW-CSE-TR-0336

TITLE: Exploring the Issues of Boundary Definition in the Application of COSMIC-FFP to Embedded Systems

AUTHOR(S): Jacky Keung, Suryaningsih, Ross Jeffery

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0336.pdf

Technical Report UNSW-CSE-TR-0337

TITLE: Present Scenarios and Future Challenges in Pervasive Middleware

AUTHOR(S): Amitava Mukherjee

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0337.pdf

Technical Report UNSW-CSE-TR-0401

TITLE:   A CDMA-Based, Self-Organizing, Location-Aware Media Access Control Protocol

AUTHOR(S):  Bao Hua (Michael) Liu

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0401.pdf

Technical Report UNSW-CSE-TR-0402

TITLE: Case Study to Monitor Cane Toads in Kakadu National Park

AUTHOR(S): Saurabh Shukla, Nirupama Bulusu, Sanjay Jha

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0402.pdf

Technical Report UNSW-CSE-TR-0403

TITLE: Design Recovery of Real-Time Graphical Applications using Video

AUTHOR(S): Kim Cuong Pham, Tran Quan Pham, Amir Michail

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0403.pdf

Technical Report UNSW-CSE-TR-0404

TITLE: Approaches for Radio Resource Management in Mobile Wireless Networks: Current Status and Future Issues

AUTHOR(S): Amitava Mukherjee

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0404.pdf

Technical Report UNSW-CSE-TR-0405

TITLE: Present Issues & Challenges in Survivable WDM Optical Mesh Networks

AUTHOR(S): Amitava Mukherjee Asidhara Lahiri Debashis Saha

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0405.pdf

Technical Report UNSW-CSE-TR-0406

TITLE: NightOwl: Self-Localisation by Matching Edges

AUTHOR(S): Raymond Sheh Bernhard Hengst

ABSTRACT

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. ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0406.pdf

Technical Report UNSW-CSE-TR-0408

TITLE: Multicast Resilience with Quality of Service Guarantees

AUTHOR(S): William Lau and Sanjay Jha

ABSTRACT

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 ex