The demand for mobile communications is continuing to grow, but there is a limit on the radio frequency resources. Micro cellular systems are a strong solution to this problem. However, Forced Call Termination (FCT) and Channel Changing (CC) occur frequently in these systems because of their small cell size. This paper proposes a new Dynamic Channel Assignment (DCA) strategy which uses information of moving direction of Mobile Stations (MSs) to reduce FCT and CC. This strategy, the MD (Moving Direction) strategy, is compared with other major DCA strategies by simulating a one-dimensional service area covering a road, such as an expressway. The simulation shows that the MD strategy performs better than the other strategies with regard to FCT, CC, and carried load. FCT is an especially important factor in the quality of service. The MD strategy reduces FCT and has the largest carried load of the strategies, which means that it has the most efficient channel usage. This is an attractive characteristic of the MD strategy for micro cellular systems.

For the connection request procedure in mobile communication systems, a previous study had shown that the 3-channel systems provide the haighest maximum of stable per channel throughput. In this paper, we propose and study a new algorithm, called the Parallel Collision Resolution Algorithm, which can be implemented in a Q-channel connection request environment, where Q3. For the implementation, the channels are arranged in R groups, where R is a positive integer. The collision resolution scheme distributes the collided messages over all the groups so that throughput and delay measures can be improved. At any point in time, there can be a maximum of R collision resolution schemes operational irrespective of the channel or the group number over which collisions occurred. The performance measures are estimated by computer simulation. Under the new algorithm, almost the same level of the perchannel stable throughput measure of a 3-channel network can be achieved in networks for which Q3. This feature allows freedom to the network designer to employ a higher number of connection request channels without forfeiting high channel utilization rates. When Q is an integral multiple of 3, the maximum stable per channel throughput level achieved can be the same as that achieved by the 3 channel system, if the grouping of channels is such that each group consists of 3 channels. When Q is not an integral multiple of 3, the intuitive strategy of organizing the channels in such a way that Q/3 groups consist of 3 channels each and one group consists of (Q mod 3) channels, may result in much degraded performance. It is found that, if the channels are so organised that no group is composed of (Q mod 3) channels, the performance levels can be substantially enhanced. Also, under the new algorithm, the delay measure is significantly improved, particularly in schemes like the mobile satellite systems with high propagation delays. We conclude that the new scheme presents a promising collision resolution methodology for connection request procedures.

The embedded Markov processes associated with Markovian queueing systems are closely related, and their relationships are important for establishing an analytical basis for performance evaluation techniques. As a first step, we analyze the embedded processes associated with a general M/M/1 queueing system. Linear transformations between the infinitesimal generators and the transition probability matrices of embedded processes at arrival and departure times are explicitly derived. Based upon these linear transformations, the equilibrium distributions of the system states at arrival and departure times are obtained and expressed in terms of the equilibrium distribution at arbitrary times. The approach presented here uncovers an underlying algebraic structure of M/M/1 queueing systems, and establishes an algebraic methodology for analyzing the equilibrium probabilities of the system states at arrival and departure times for more general Markovian queueing systems.

Modeling and performance analysis have played an important role in the economical design and efficient operation of switching systems, and is currently becoming more important because the switching systems should handle a wide range of traffic characteristics, meeting the grade of service requirements of each traffic type. Without these techniques we could no longer achieve economy and efficiency of the switching systems in complex traffic characteristic environments. From the beginning of research on electronic switching systems offering circuit-switched applications, Stored Program Control (SPC) technology has posed challenges in the area of modeling and performance analysis as well as queueing structure, efficient scheduling, and overload control strategy design. Not only teletraffic engineers and performance analysts, but also queueing theorists have been attracted to this new field, and intensive research activities, both in theory and in practice, have continued over the past two decades, now evolving to even a broader technical field including traditional performance analysis. This article reviews a number of important issues that have been raised and solved, and whose solutions have been reflected in the design of SPC switching systems. It first discusses traffic problems for centralized control systems. It next discusses traffic problems inherent in distributed switching systems.

In this paper we present and analyze multi-level quorum schemes for maintaining the consistency of replicated data in the presence of concurrency and failures in a large distributed environment. The multi-level quorum method operates on a logical hierarchy of the nodes in the network and applies well known flat voting algorithms for replicated data concurrency control in a layered fashion. We show how the number of hierarchy levels, the number of logical entities per level and the voting algorithms used on each level affect the costs and the degree of availability associated with a wide range of multi-level quorum schemes. The results of the analysis are used to provide guidelines for designing the most suitable multi-level quorum strategy for a given application scenario. Comparative performance measurements in a simulated network are presented to illustrate the properties of multi-level approaches when some of the assumptions of the analytical investigation do not hold.

Synchronous clocks are an essential requirement for a variety of distributed system applications. Many of these applications are safety-critical and require fault tolerance. In this paper, a general probabilistic clock synchronization model is presented. This model is uniformly probabilistic, incorporating random message delays, random clock drifts, and random fault occurrences. The model allows faults in any system component and of any type. Also, a new Sliding Window Clock Synchronization Algorithm (SWA) providing increased fault tolerance is proposed. The probabilistic model is used for an evaluation of SWA which shows that SWA is capable of tolerating significantly more faults than other algorithms and that the synchronization tightness is as good or better than that of other algorithms.

In developing the SXO operating system for the SURE SYSTEM 2000 continuous operation system, we aimed to create an unprecedentedly high software and hardware fault tolerance. We devised a fault tolerant architecture and various methodologies to ensure fault tolerance. We implemented these techniques systematically throughout operating system development. In the design stage, we developed a design methodology called the recovery process chart to verify that recovery mechanisms were complete. In the manufacturing stage, we applied the concept of critical routes to recovery and other processes essential to high dependability. We also developed a method of finding critical routes in a recovery process chart. In the test stage, we added an artificial software fault injection mechanism to the operating system. It generates various reproducible errors at appropriate times and reduces the number of personnel needed for test, making system reliability evaluation easy.

The pressure waveforms indicated on a catheter manometer system are subject to serious distortion due to the resonance of the catheter itself, or the compliance of a particular transducer. Although several methods have been proposed for improving those characteristics, they ahave never been put into practice. We have focused on the transfer function of the catheter manometer, and made a pilot system, using the natural observation method. This method has been suggested as a means of studying the structure of the instantaneous waveform. In this manner, we were able to increace the bandwidth in the ferquency domain and reduce the ringing in the time domain. Correction was performed automatically, using a step wave. Reproduction of the waveform with a flushing device, was a task of equal simplicity, that allowed us to estimate the system parameters so that the response waveform became step-like. In the experiment, our system provided distortion-free left-ventricular pressure waveform measurements and exact evaluation of the cardiac pumping system. The values obtained came much closer to the original figures arrived at by the catheter-tip manometer system.

This paper describes a programming system, K-NET for the development of control software for flexible manufacturing systems composed of robots, numerically-controlled machines, transfer machines and automatic storage/retrieval systems. K-NET is based on a high-level Petri net which makes it simple to express operational functions such as synchronization, interlock and concurrence in sequence control. Petri net in K-NET is colored one in which tokens have attributes, and timed one which can provide a notion of stochastic time. K-NET provides many kinds of boxes having specific functions, and gates specified the firing condition and the token flow control with IF-THEN rules. On the other hand, procedural language can be also used for information processing. K-NET can support all development stages including general design, detailed design, programming and testing. K-NET has an editor to input control specifications expressed with Petri net; a simulator to verify edited specifications; a generator to convert the net to C source programs for a computer or to ladder diagrams for a programmable controller; a reporter to print control specifications; and a monitor to display controller status in real-time. K-NET has been used in the development of control software for an automated guided vehicle system, and results show a 2/3rds cost-saving over development with conventional methods in which only procedural language is used.

A job shop system typically seen in flexible manufacturing systems (FMS) is a system composed of a set of machines and a various kind of jobs processed with the machines. A production system of semiconductor fabrication is an example of job shop systems, which has main features of repetitive processes of one part and set-up times required for machines processing different types of parts. On the other hand, timed Petri nets are used for modelling and analyzing a wide variety of discrete event systems. There are many applications of timed Petri nets to the scheduling problems of job shop systems. The performance evaluation and steady state behaviors are studied by using the maximum cycle time of timed marked graphs. The aim of this paper is to propose a new model for production systems including repetitive processes and set-up time requirements which enables the quantitative analysis of real time system performance. In job shop systems such as a semiconductor fabrication system, it takes considerable amount of set-up time to prepare different types of chemical reactions and the model should take account of a set-up time for each machine. We focus upon the relationship between facility utilization factor and production cycle time in the steady state. In the proposed model, the minimum total set-up time can be attained. Quantitative relationship between utilization factor and production cycle time is derived by using the proposed model. A utilization factor of a system satisfying a given limit of the cycle time is evaluated, and the improvement of the utilization factor is considered. Conversely, we consider the improvement of the cycle time of a system satisfying a given limit of utilization factor.

The paper describes a novel 32-bit RISC microprocessor architecture for embedded systems. Variable-length instructions of 16, 32 or 48 bits provide compact code since the majority of instructions are 16 bits in length. The basic instruction format of 16 bits allows only 2 register adresses of 5 bits each; however, it is shown that the overhead in the instruction count is only between 14% and is far outweighed by the savings in program size. The register set provides addressing of 16 global and up to max. 16 local registers per stack frame in a register stack of 64 registers. The stack frames are of variable length with a variable overlap for parameter passing. A load/store architecture is used; memory accesses are pipelined. Nearly all instructions execute in a single cycle. A two-stage pipeline (decode/execute) minimizes wait cycles after pipeline breaks due to branches. An instruction cache of 128 bytes employs an efficient look-ahead algorithm and is quickly updated in case of a cache miss. The µP is implemented in 1.2 µm CMOS on a die of 47 mm2. Power dissipation is only 0.5 W. The development environment is PC-based.

The pursuit of higher availability has resulted in the development of fault tolerant systems for many industries. However, system characteristics that can be perceived by the customer have never been diagnosed quantitatively. This paper considers the application of stochastic Petri nets with general firing times to modeling of a fault tolerant system and the use of discrete-event simulation methods for stochastic Petri nets to study the behavior of the system. The stochastic Petri net model incorporates factors that compose the system as well as those that accompany it, including RAS characteristics of products, personnel arrangements, and system management. By modeling the behavioral aspect of each factor, it is possible to diagnose a fault tolerant system quantitatively on the basis of customer impact.

This paper describes MENDELS ZONE, a Petri-net-based concurrent programming environment, which is especially suitable for cooperating discrete event systems. MENDELS ZONE adopts MENDEL net, which is a type of high level (hierarchical colored) Petri net. One of the characteristics of the MENDEL nets is a process-oriented hierarchy like CCS, which is different from the subnet-oriented hierarchy in the Jensen's hierarchical colored Petri net. In a process-oriented hierarchy, a hierarchical unit is a process, which is more natural for cooperating and decentralized discrete event control systems. This paper also proposes a design methodology for MENDEL nets. Although many Petri net tools have been proposed, most tools support only drawing, simulation, and analysis of Petri nets; few tools support the design methodology for Petri nets. While Petri nets are good final design documents easy to understand, analyzable, and executable it is often difficult to write Petri nets directly in an earlier design phase when the system structure is obscure. A proposed design methodology makes a designer to construct MENDEL nets systematically using causality matrices and temporal logic. Furthemore, constructed MENDEL nets can be automatically compiled into a concurrent programming language and executed on a parallel computer.

In order to make the implementation of network components flexible and cost effective, it is required to use widely available technologies as the implementation platform. The distributed operating systems can be adopted as such a platform, because they allow to implement a network component using multiple computers connected through a local area network. In this paper, we focus on the Intelligent Network (IN) whose network components are modelled as Functional Entities (FEs), and describe an implementation method of FEs using distributed operating systems. Our method is summarized as follows: The remote procedure call (RPC) is used for the access transparent inter-process communication. The lightweight process mechanism is used for handling concurrent requests. CCF/SSF (Call Control Function/Service Control Function) and SDF (Service Data Function) are implemented as an SSF server and an SDF server, respectively. SCF (Service Control Function) is composed of a Service Dispatcher and a set of Service Executors. The Service Dispatcher accepts all the requests for IN call processing and dispatches them to appropriate Service Executors. Service Executors are created for the individual IN services and execute the service logics. SDF server and Service Executor may be replicated for load partitioning.This paper has also described the implementation of experimental system supporting "Freephone" service based on our method, and showed the performance evaluation of the experimental system in terms of the real-time and concurrent call processing of IN services. We used Mach and SUN OS as a platform for implementing the servers for FEs. The experimental system using four workstations shows that it can handle up to 170IN calls in one second with the additional response time of less than 200msec, which is small enough compared with the response time for the basic connection control. Those results prove that our method is feasible for implementing practical FEs.

Recent trends in down-sizing have resulted in the development of client server systems for many industries. This paper considers the application of stochastic Petri nets with general firing times for modeling of a concatenated client server system and the use of discrete-event simulation methods for stochastic Petri nets to study its behavior. This approach enables us to assess the most appropriate resource set of a concatenated client server system on the quantitative basis of the performability and the occurrence of system down conditions. Thus, system consultation, a new application of stochastic Petri nets, is presented.

Advances in semiconductor technology have made it possible to develop an experimental 1000 MIPS superscalar RISC processor. The high performance of this processor was obtained using architectural concepts such as multiple CPU configuration, superscalar microarchitecture, and high-speed device technology. This paper focuses on the novel features of this RISC processor, its device technology, architectural characteristics and one technology that has been devised to make its integer CPU cores fault-tolerant.

An integrated platform INTEGRAL has been developed for developing large complex communication software systems. At the heart of INTEGRAL, a pair of graphical and textual specification languages, DISCOL (DIStributed Communication-Oriented Language), has been developed based on Petri nets. Around DISCOL, a wide variety of design and analysis tools have been integrated in coherent manner so that a seamless support from design to verification and testing are made available along with software life-cycle. The platform has been applied to the development of a PBX simulator named UICPBX. In the development, some real communication services have been fully specified with DISCOL. Such experiences have revealed the effectiveness of the proposed techniques.

Stochastic Petri Nets and Generalized Stochastic Petri Nets as well as other extensions to Stochastic Petri Nets have been widely applied as a model of asynchronous concurrent process, or as an aid to analyze or design concurrent systems. This paper presents an Extended Stochastic Petri Net model for a shift processing system in which three kinds of sink may occur and an arbitrary time distribution is incorporated, provides an analytical method based on a Markov renewal process with some non-regeneration points to clarify the probabilistic behavior of the system, and finally evaluates the performance of the system with numerical values.

This paper presents a method for LSI implementation of a long-tap acoustic echo canceller algorithm using the residue number system (RNS) and the mixed-radix number system (MRS). It also presents a quantitative comparison of echo canceller architectures, one using the RNS and the other using the binary number system (BNS). In the RNS, addition, subtraction, and multiplication are executed quickly but scaling, overflow detection, and division are difficult. For this reason, no echo canceller using the RNS has been implemented. We therefore try to design an echo canceller architecture using the RNS and the NLMS algorithm. It is shown that the echo canceller algorithm can be effectively implemented using the RNS by introducing the MRS. The quantitative comparison of echo canceller architectures shows that a long-tap acoustic echo canceller can be implemented more effectively in terms of chip size and power dissipation by the architecture using the RNS.

This paper describes a new method for designing switching software called DDL (Data Driven Logic). The new design method adopts the dataflow concept and graphical programming using a dataflow diagram. A dataflow diagram is used for software representation, and a dataflow mechanism is emulated on a conventional von Neumann processor. The DDL method has the following advantages; (1) general advantages of dataflow software; i.e. easily understandable programs using graphical representations, and easy description of parallelism, (2) modular design using reusable software components, (3) easy design and programming with a graphical user interface. This paper presents the general concepts and structure of DDL. It also discusses the dataflow emulation mechanism, the DDL software development process, the DDL programming environment, an evaluation of the DDL call processing program applied to a commercial PABX, and some unsolved problems of DDL.