This paper aims at improving effectiveness of previously proposed hybrid priority lists, {L*i=LdLsi}, that are applied in nonpreemptive 2-processor scheduling of general acyclic SWITCH-less program nets, where Ld and Lsi are dynamic and static priority lists respectively. Firstly, we investigate the effectiveness of Ld through experiments. According to the experimental results, we reconstruct Ld to propose its improved list L1d. Then analyzing the construction methodology of the static priority lists {Lsi}, we propose a substituted list L2d by taking into account of the factor: remaining firing numbers of nodes. Finally, we combine a part of L1d and L2d to propose a new priority list L**. Through scheduling simulation on 400 program nets, we find the new priority list L** can generate shorter schedules, close to ones of GA (Genetic Algorithm) scheduling that has been shown exceedingly effective but costing much computation time.

An inverse scattering problem in three dimensional two layered media is investigated. The shape and the location of the acoustic scatterer buried in one half-space are determined. With some a priori information, it becomes possible to solve this problem in three dimensions. Using the moment method, the scattered field is obtained for the estimated scatterer. An iterative procedure based on the Newton's method for the nonlinear least square problem is able to solve the inverse scattering problem. Some numerical results are presented.

We investigate traffic performance of CBWL schemes with multimedia services on non-homogeneous cellular network in which cut-off priority is given to handoff calls. Two generic routing schemes are analyzed: one is the randomized routing and the other is the least loaded routing. The performance measures that we focus on are the new call blocking probabilities and the handoff failure probabilities. To evaluate blocking probabilities of interest, we construct a generalized access network whose blocking probabilities are same as ones for CBWL systems. For analysis of generalized access network, we apply the reduced load approximation. The computational complexity and memory requirements of proposed algorithm are linear so that we can use this algorithm to approximate blocking probabilities of CBWL systems of large size. The proposed approximations are tested on a number of simple examples. Numerical results for 12 cells and 36 cells networks are given. The comparison between approximation and simulation results shows that the proposed approximation method is quite accurate.

When a mobile station with a call in progress moves across cell boundary in a cellular mobile communications system, the system must switch the circuit to the base station in the destination cell to enable uninterrupted communications in a process called "handoff. " However, if a circuit to the destination base station cannot be secured when a handoff is attempted, the call is forcibly terminated. Studies have therefore been performed on methods of decreasing the percentage of forcibly terminated calls by giving handoff calls priority. With the aim of simplifying system design, we propose a system for automatically setting the number of circuits reserved for handoff based on the handoff block rate. In this paper, we describe this system and evaluate static traffic characteristics taking into account reattempt calls, the occurrence of which can have a major effect on system performance. We also consider the effects of the proposed system on service quality since giving priority to handoff calls and decreasing the rate of forced terminations results in a tradeoff with the blocking rate of new call attempts. Finally, we evaluate the traffic characteristics associated with the number of control requests, an important element in estimating the processing capacity required by control equipment at the time of system design.

This paper deals with two-processor scheduling for general acyclic SWITCH-less program nets with random node firing times. First, we introduce a hybrid priority list L* that has been shown to generate optimal schedules for the acyclic SWITCH-less program nets with unity node firing times, of which AND-nodes possess at most single input edge. Then considering the factors of existence of the AND-nodes with two input edges as well as random node firing times, we extend L* to design a new dynamic priority list Ld and four static priority lists {Lsii=1,2,3,4}; and then combining Ld and Lsi (i=1,2,3,4) we propose four hybrid priority lists {L*ii=1,2,3,4}. Finally, we apply genetic algorithm to evaluate the schedules generated by the four lists through simulations on 400 program nets. Our simulation results show two of the four lists can generate reasonably good schedules.

This paper deals with two-processor scheduling for a class of program nets, that are acyclic and SWITCH-less, and of which each node has unity node firing time. Firstly, we introduce a hybrid priority list L* that generates optimal schedules for the nets whose AND-nodes possess at most single input edge. Then we extend L* to suit for general program nets to give a new priority list L**. Finally, we use genetic algorithm to do the performance evaluation for the schedules generated by L** and show these schedules are quite close to optimal ones.

For backup of failed VPs (Virtual Paths) in ATM (Asynchronous Transfer Mode) networks, many self-healing algorithms have already been proposed. However, since the existing algorithms recover each failed VP with a single backup VP, a problem arises in that those algorithms cannot necessarily provide a failed VP having a higher recovery priority with a larger recovery ratio, which is the ratio of the bandwidth of a backup VP to that of a failed VP. For a solution to the problem, this paper proposes a new self-healing algorithm which recovers each failed VP with one or more backup VPs. We also evaluate its availability by comparing with an existing algorithm through simulations.

In this paper, we propose a preemptive priority handoff scheme for integrated voice/data cellular mobile systems. In our scheme, calls are divided into three different classes: handoff voice calls, originating voice calls, and data calls. In each cell of the system there is a queue only for data calls. Priority is given to handoff voice calls over the other two kinds of calls. That is, the right to preempt the service of data is given to a handoff voice call if on arrival it finds no idle channels. The interrupted data call returns to the queue. The system is modeled by a two-dimensional Markov chain. We apply the Successive Over-Relaxation (SOR) method to obtain the equilibrium state probabilities. Blocking and forced termination probabilities for voice calls are obtained. Moreover, average queue length and average transmission delay of data calls are evaluated. The results are compared with another handoff scheme for integrated voice/data cellular mobile systems where some numbers of channels are reserved for voice handoff calls. It is shown that, when the data traffic is not very light, the new scheme can provide lower blocking probability for originating voice calls, lower forced termination probability for ongoing voice calls, and shorter average queue length and less average transmission delay for data calls.

A partial buffer sharing scheme is proposed as loss-priority control for a finite buffer with batch Poisson inputs under a whole batch acceptance rule. Customer and batch loss probabilities for high- and low-priority customers are derived under this batch acceptance rule using a supplementary variable method. A comparison of the partial buffer sharing scheme and a system without loss-priority control is made in terms of admissible offered load. Whole batch acceptance and partial batch acceptance rules are also compared in terms of admissible offered load.

From our previous studies, we derived the worst case cell delay within an ATM switch and thus can find the worst case end-to-end delay for a set of real-time connections. We observed that these delays are sensitive to the priority assignment of the connections. With a better priority assignment scheme within the switch, the worst case delay can be reduced and provide a better network performance. We extend our previous work on the closed form analysis to conduct more experimental study of how different priority assignments and system parameters may affect the performance. Furthermore, from our worst case delay analysis on a regulated ATM switch, network traffic can be smoothed by a leaky bucket at the output controller for each connection. With the appropriate setting on the leaky bucket parameter, the burstiness of the network traffic can be reduced without increasing the delay in the switch. Therefore, fewer buffers will be required for each active connection within the switch. In this paper, our experimental results have shown that the buffer requirement can be reduced up to 5.75% for each connection, which could be significant, when hundreds of connections are passing through the switches within a regulated ATM network.

IEEE 802. 11 is a standard for wireless LANs. The basic access method in its MAC layer protocol is the distributed coordination function (DCF) for the ad hoc networks. It is based on the mechanism of carrier sense multiple access with collision avoidance (CSMA/CA). DCF is used to support asynchronous data transmission. However, frames in DCF do not have priorities, making it unsuitable for real-time applications. With a little bad luck, a station might have to wait arbitrarily long to send a frame. In this paper, we propose a method to modify the CSMA/CA protocol such that station priorities can be supported. The method is simple, efficient and easy to implement in comparison to point coordination function (PCF), another access method in IEEE 802. 11 based on access points (base stations). Simulations are conducted to analyze the proposed scheme. The results show that DCF is able to carry the prioritized traffic with the proposed scheme.

In this paper, we present a priority scheduling algorithm at ATM switches with multi-class output buffers in which the service rate of each class buffer is dynamically adjusted. The service rate is computed periodically by a control scheme. We derive the design formulas of the control scheme to ensure that each class buffer occupancy converges to its desired operating point related to QoS requirement. Moreover, through dynamic service rate control in the proposed scheduling algorithm, the available channel capacity can be estimated exactly. It may be used for rate control of ABR traffic and call admission control of the other real-time traffic (CBR, VBR, etc. ).

This paper investigates an ATM multiplexer with a resume level, which uses a selective cell discarding strategy as a priority control, and a Markov-modulated deterministic process (MMDP) as the burst input traffic. Assuming that a system is loaded with a superposition of several independent and homogeneous On-Off bursty sources with two priority classes, we obtain the cell loss probability of each priority class of an ATM multiplexer with a resume level. The performance analysis derived here includes as special cases one without priority and one with a threshold level. From the numerical results, we compare the cell loss probability, the mean queue length, the mean queuing delay, the level crossing rate, and the queue length distribution at the embedded points for the case of a threshold level with those for the case of a resume level. By selecting an appropriate resume level, we can reduce the sensitive state change around the threshold level.

Priority control and call admission control are indispensable traffic management methods to guarantee each QoS requirement of connections in ATM networks. The key technique of call admission control under priority control is to estimate required bandwidth of each connection to satisfy all QoSs of calls in progress. In this paper, we propose a novel approximation method to calculate the required bandwidth of ATM connections through priority queues and show a practical call admission control scheme using the proposed method. The essence of the approximation method is to model prioritized parallel queues as a series of queues in tandem with no priority control by focusing on the number of cells in queues. The tandem queue approximation method enables us to model each queue under priority control as a single non-priority FIFO queue in terms of its queue length. This results in that effective bandwidth techniques are applicable to priority queues. The effectiveness of the proposed scheme is evaluated by some numerical examples.

An enhanced priority reservation algorithm for ATM multicast switches with a one-shot scheduling scheme is proposed. This algorithm is an input reservation method in which priority is selected among input ports considering the number of rejected copy requests and the blocked age of head-of-line (HOL) cells. The operation procedure of the proposed algorithm is described, and the average cell-delay and throughput performance is evaluated by simulation. The simulation results show that the proposed algorithm yields better performance than the conventional algorithms.

A partial buffer sharing scheme is proposed as loss-priority control for a finite buffer with batch inputs. A partial batch acceptance strategy is used for a batch arriving at a finite buffer. Customer loss probabilities for high- and low-priority customers are derived under this batch acceptance strategy, using a supplementary variable method that is a standard tool for queueing analysis. A comparison of the partial buffer sharing scheme and a system without loss-priority control is made in terms of admissible offered load.

In the commonsense reasoning, priorities among rules are often required to be found out in order to derive the desired conclusion as a theorem of the reasoning. In this paper, first we present the bottom-up and top-down abduction procedures to compute skeptical explanations and secondly show that priorities of circumscription to infer a desired theorem can be abduced as a skeptical explanation in abduction. In our approach, the required priorities can be computed based on the procedure to compute skeptical explanations provided in this paper as well as Wakaki and Satoh's method of compiling circumscription into extended logic programs. The method, for example, enables us to automatically find the adequate priority w. r. t. the Yale Shooting Problem to express a human natural reasoning in the framework of circumscription.

This paper presents a finite buffer M/G/1 queue with two classes of customers who are served by a combination of head-of-the-line priority and buffer reservation schemes. This combination gives each class of customers high or low priorities in terms of both delay and loss. The scheme is analyzed for the model in which one class of customers has high priorities over the other class of customers with respect to both delay and loss. First, steady-state joint probability distribution of the number of each class of customers in the buffer and remaining service time is derived by a supplementary variable method. Second, loss probability and mean waiting time for each class of customers are provided using this probability distribution. Finally, a combination of head-of-the-line priority and buffer reservation schemes is numerically compared with other buffer management schemes in terms of admissible offered load to show its effectiveness under differing QoS requirements.

Asynchronous Transfer Mode (ATM) networks are expected to support a diverse mix of traffic sources requiring different Quality Of Service (QOS) guarantees. This paper initially examines several existing scheduling disciplines which offer delay guarantees in ATM switches. Among them, the Earliest-Due-Date (EDD) discipline has been regarded as one of the most promising scheduling disciplines. The EDD discipline schedules the departure of a cell belonging to a call based on the delay priority assigned for that call during the call set-up. Supporting n delay-based service classes through the use of n respective urgency numbers D0 to Dn-1 (D0D1 Dn-1), EDD allows a class-i cell to precede any class-j (j>i) cell arriving not prior to (Dj-Di)-slot time. The main goal of the paper is to determine the urgency numbers (Dis), based on an in-depth queueing analysis, in an attempt to offer ninety-nine percentile delay guarantees for higher priority calls under various traffic loads. In the analysis, we derive system-time distributions for both high- and low-priority cells based on a discrete-time, single-server queueing model assuming renewal and non-renewal arrival processes. The validity of the analysis is justified via simulation. With the urgency numbers (Dis) determined, we further propose a feasible efficient VLSI implementation architecture for the EDD scheduling discipline, furnishing the realization of QOS guarantees in ATM switches.

We present a new scheduling policy named Value-based Processor Allocation (VPA-k) for scheduling value-based transactions in a multiprocessor real-time database system. The value of a transaction represents the profit the transaction contributes to the system if it is completed before its deadline. Using VPA-k policy, the transactions with higher values are given higher priorities to execute first, while at most k percentage of the total processors are allocated to the urgent transactions dynamically. Through simulation experiments, VPA-k policy is shown to outperform other scheduling policies substantially in both maximizing the totally obtained values and minimizing the number of missed transactions.