Abstract not available

The Resource Reservation Protocol (RSVP) is one of the proposals of the Internet Engineering Task Force (IETF) for conveying Quality of Service (QoS) related information in the form of resource reservations along the communication path. The RSVP specification (i.e. Request for Comments 2205) provides a narrative description of the protocol without any use of formal techniques. Thus, some parts of the document may be ambiguous, difficult to understand, and imprecise. So far, RSVP implementations have provided the only mechanism for validating. The cost for fixing errors in the protocol found in the implementation can be high. These disadvantages together with the fact that RSVP is complex make it a good target for formal specification and verification. This thesis formally defines the RSVP Service Specification, models RSVP using a formal method known as Coloured Petri Nets (CPNs) and attempts to verify the model. The following steps summarise the verification process of RSVP. Firstly, the RSVP service specification is derived from the protocol description and modelled using CPNs. After validating the model, the service language, which defines all the possible service primitive occurrence sequences, is generated from the state space of the model by using automata reduction techniques that preserve sequences. Secondly, RSVP is modelled using CPNs. The model is analysed for a set of behavioural properties. They include general properties of protocols, such as correct termination, and a set of new properties defined in this thesis, which are particular to RSVP. The analysis is based on the state space method. The properties are checked by querying the state graph and checking reachability among multiple nodes of its associated Strongly Connected Component (SCC) graph. As a first step, we analyse RSVP under the assumption of a perfect medium (no loss or duplication) to ensure that protocol errors are not hidden by rare events of the medium. The state space is reduced to obtain the sequences of service primitives allowed by RSVP known as the protocol language. Then, the protocol language is compared with the service language to determine if they are equivalent. The desired properties of RSVP are proved to be satisfied by the RSVP CPN model, so that the features of RSVP included in the CPN model operate as expected under our modelling and analysis assumptions. Also, the language analysis results show that RSVP service primitive occurrence sequences generated by the RSVP model are included in the proposed model of the service specification. However, some service primitive occurrence sequences generated from the service specification model are not in the protocol language. These sequences were analysed. There is strong evidence to suggest that these sequences would also appear in the protocol if the capacity of the medium in the RSVP model was marginally increased. Unfortunately, the standard reachability analysis tools would not handle this case, due to state space explosion. / Thesis (PhD)--University of South Australia, 2003

This thesis investigates an innovative framework and process coordination technologies for peer-to-peer based decentralised workflow systems. The aim of this work is to address some of the unsolved problems in the contemporary workflow research rudimentally from an architectural viewpoint. The problems addressed in this thesis, i.e., bad performance, vulnerability to failures, poor scalability, user restrictions, unsatisfactory system openness, and lack of support for incompletely specified processes, have become major obstacles for wide deployment of workflow in real-world. After an in-depth analysis of the above problems, this thesis reveals that most of these problems are mainly caused by the mismatch between application nature, i.e., distributed, and system design, i.e., centralised management. Thus, the old-fashioned client-server paradigm which is conventionally used in most of today�s workflow systems should be replaced with a peer-to-peer based, open,collaborative and decentralised framework which can reflect workflow�s distributed feature more naturally. Combining workflow technology and peer-to-peer computing technology, SwinDeW which is a genuinely decentralised workflow approach is proposed in this thesis. The distinguished design of SwinDeW removes both the centralised data repository and the centralised workflow engine from the system. Hence, workflow participants are facilitated by automated peers which are able to communicate and collaborate with one another directly to fulfil both build-time and run-time workflow functions. To achieve this goal, an innovative data storage approach, known as �know what you should know�, is proposed, which divides a process model into individual task partitions and distributes each partition to relevant peers properly according to the capability match. Based on such a data storage approach, the novel mechanisms for decentralised process instantiation, instance execution and execution monitoring are explored. Moreover, SwinDeW is further extended to support incompletely-specified processes in the decentralised environment. New technologies for handling incompletely-specified processes at run-time are presented. The major contributions of this research are an innovative, decentralised workflow system framework and corresponding process coordination technologies for system functionality. Issues regarding system performance, reliability, scalability,user support, system openness, and incompletely-specified process support are discussed deeply. Moreover, this thesis also contributes the SwinDeW prototype which implements and demonstrates this design and functionality for proof-of concept purposes. With these outcomes, performance bottlenecks in workflow systems are likely to be eliminated whilst increased resilience to failure, enhanced scalability, better user support and improved system openness are likely to be achieved with support for both completely- and incompletely-specified processes. As a consequence, workflow systems will be expected to be widely deployable to real world applications to support processes, which was infeasible before.

[No Abstract]

The primary objective of this research is to develop a network-centric simulation modeling framework that can be used to build simulation models through the use of Internet-based resources. An object-oriented programming approach was used to build a Java-based modeling framework focused on modeling a semiconductor fabrication system. This research is an initial step in what may be a new network-centric simulation modeling methodology, where simulation models are created using software objects that are physically located in many different sites across the Internet. Once the ability to create and run a relatively simple model using a network-centric approach has been established, future research may lead to a simulation environment that not only lets a user interactively build models but also allows concurrent model development between a group of users, independent of their location, operating system, or computer architecture. The prototype system implemented as a portion of this research is performed in the Java object-oriented programming language. A target system model is presented as an example of how the environment can be used to apply the network-centric simulation modeling methodology. / Graduation date: 1998

Many different types of distributed batch scheduling systems have been developed in the last decade to take advantage of the decentralization of computers and the enormous investments that many companies and educational institutions have in desktop workstations. Based on the premise that the majority of desktop workstations are significantly underutilized, distributed batch systems allow users to submit and run jobs when these workstations are available. While simpler systems determine machine availability by time of day (e.g., 5:00 p.m. to 8:00 a.m.), more sophisticated systems determine availability dynamically, migrating tasks when the availability changes. Ring Leader is a distributed batch system currently under development at Hewlett Packard. Since meeting the objectives of a distributed system rely on the intelligent use of idle workstations, good resource determination and efficient utilization decisions are a high priority for such a system. System performance will depend heavily on the process of deciding where jobs should be run. This thesis explains the development of Ring Leader's history based resource utilization scheme, and compares its performance to more simplistic algorithms. / Graduation date: 1997

Parallel computing on heterogeneous workstation clusters has proved to be a very efficient use of available resources, increasing their overall utilization. However, for it to be a viable alternative to expensive, dedicated parallel machines, a number of key issues need to be resolved. One of the major challenges of heterogeneous computing is coping with the inherent heterogeneity of the system, with the availability of workstations from different vendors of varying processing speeds and capabilities. The existence of multiple jobs and users further complicates the task. The time taken for a parallel job is constrained by the time taken by the slowest or the most heavily loaded workstation. Therefore, load sharing of parallel computations is imperative in ensuring good overall utilization of the system. Since load sharing is essentially independent of the particular parallel job being run, the development of program independent, automatic, scheduling and load sharing strategies have become vital to the efficient use of the heterogeneous cluster. This thesis discusses various prior approaches to load sharing, examines a new strategy developed for heterogeneous workstations, and evaluates its performance. / Graduation date: 1996

by Dimitri P. Bertsekas. / Bibliography: leaf 15. / "August 1981." / Partial support provided by the Defense Advanced Research Projects Agency under Grant no. ONR-N00014-75-C-1183

M.S. / Computer Science / This paper deals with the problem of solving a system of sparse nonsymmetric matrices on a distributed memory multiprocessor computer, the Intel iPSC (hypercube). The processors have substantial local memory but no global shared memory. They communicate among themselves and with a host processor through message passing. The primary interest is to design an algorithm which exploits parallelism, and which performs elimination and solution of large sparse matrices. Elimination is performed by LU- decomposition. The storage scheme is based on linked list data-structure defined for a given generated matrix. The matrix is distributed by columns in a "wrapped" fashion so that elimination in the natural order will be balanced, if the sparsity structure is equally distributed across the columns. Numerical results from experiments running on the hypercube are included along with performance analysis.

Electric propulsion has recently become a viable technology for spacecraft, enabling shorter flight times, fewer required planetary gravity assists, larger payloads, and/or smaller launch vehicles. With the maturation of this technology, however, comes a new set of challenges in the area of trajectory design. Because low-thrust trajectory optimization has historically required long run-times and significant user-manipulation, mission design has relied on expert-based knowledge for selecting departure and arrival dates, times of flight, and/or target bodies and gravitational swing-bys. These choices are generally based on known configurations that have worked well in previous analyses or simply on trial and error. At the conceptual design level, however, the ability to explore the full extent of the design space is imperative to locating the best solutions in terms of mass and/or flight times. Beginning in 2005, the Global Trajectory Optimization Competition posed a series of difficult mission design problems, all requiring low-thrust propulsion and visiting one or more asteroids. These problems all had large ranges on the continuous variables - launch date, time of flight, and asteroid stay times (when applicable) - as well as being characterized by millions or even billions of possible asteroid sequences. Even with recent advances in low-thrust trajectory optimization, full enumeration of these problems was not possible within the stringent time limits of the competition. This investigation develops a systematic methodology for determining a broad suite of good solutions to the combinatorial, low-thrust, asteroid tour problem. The target application is for conceptual design, where broad exploration of the design space is critical, with the goal being to rapidly identify a reasonable number of promising solutions for future analysis. The proposed methodology has two steps. The first step applies a three-level heuristic sequence developed from the physics of the problem, which allows for efficient pruning of the design space. The second phase applies a global optimization scheme to locate a broad suite of good solutions to the reduced problem. The global optimization scheme developed combines a novel branch-and-bound algorithm with a genetic algorithm and an industry-standard low-thrust trajectory optimization program to solve for the following design variables: asteroid sequence, launch date, times of flight, and asteroid stay times. The methodology is developed based on a small sample problem, which is enumerated and solved so that all possible discretized solutions are known. The methodology is then validated by applying it to a larger intermediate sample problem, which also has a known solution. Next, the methodology is applied to several larger combinatorial asteroid rendezvous problems, using previously identified good solutions as validation benchmarks. These problems include the 2nd and 3rd Global Trajectory Optimization Competition problems. The methodology is shown to be capable of achieving a reduction in the number of asteroid sequences of 6-7 orders of magnitude, in terms of the number of sequences that require low-thrust optimization as compared to the number of sequences in the original problem. More than 70% of the previously known good solutions are identified, along with several new solutions that were not previously reported by any of the competitors. Overall, the methodology developed in this investigation provides an organized search technique for the low-thrust mission design of asteroid rendezvous problems.