Bluetooth is a radio interface standard used to build a personal area ad-hoc network(PAN) by interconnecting mobile electronics devices. In PAN, different applications and protocols place different QoS demands on the link. To meet these requirements properly, Bluetooth specification provides quality of service(QoS) configuration. In particular, Bluetooth LMP commands are used to configure the poll interval to provide QoS service to the higher layer. However, a method to provide QoS in scatternet is absent in the specification. Moreover, in scatternet, the schedule exerts a direct influence on the basic QoS properties like bandwidth, delay and jitter. We present two versions of QoS-aware scheduling algorithms: a perfect assignment algorithm for bipartite scatternet and a distributed, local algorithm. Also, both algorithms are shown to be perfect over tree scatternet. Finally, we present the performance and QoS evaluation. It is shown that the delay and jitter of the schedule generated by the algorithms have tight bounds.

We present an object-oriented programming platform applicable to any real-time distributed telecommunication system. The proposed platform is constructed upon the extended version of the real-time, distributed operating system, SROS (Scalable Real-time Operating System), that is developed at ETRI and successfully operating in the ATM switching system for several years. The object-oriented software development and maintenance methodology will resolve the current software crisis in the area of telecommunication and switching systems due to the everlasting maintenance of the huge amount of the existing software and the ever increasing needs for the better and new communication services. In general, an object-oriented software platform realizes the object-oriented methodology and possesses many good aspects like high productivity, better reusability, easy maintenance, et al., but in the expense of the operation overhead that would decrease the system performance significantly. To counteract this problem, in the design of each integral part of the platform, we considered the real-time property as the most important design criterion. The platform is also designed to present a distributed multimedia service in addition to real-time event delivery. We have been implementing a couple of prototypes based on the proposed platform. Reflecting the evaluation result on these prototypes, the final platform specification is determined.

A software retrofit method, stand-by loading scheme, is proposed for a switching system in which the service downtime should be suppressed under several minutes per year. In general, software upgrade is performed in the system suspension state. However, in a switching system, it should be exercised without breaking the service continuity and minimize the possible side effects against on-going services. Stand-by loading scheme satisfies such a requirement in addition to the high efficiency in the maintenance and repair, and easy upgrade of additional functions of a switching system, and thus makes the system to evolve easily. Currently, a switching system adopting this method was constructed and has been used successfully in the field.

Probes and tokens are used in many deadlock detection and resolution algorithms. A deadlock is detected by propagating probes along dependency edges. When the initiator p/sub i/ of a probe receives its probe back, it knows of the existence of a deadlock. p/sub i/ then sends out a token to clean up those probes in the deadlock; cycle which, if not removed, may later lead to phantom deadlock detections. Only after the token returns to p/sub i/ is the deadlock resolved by aborting a 'victim' (usually p/sub i/). As a result, all involved transactions remain waiting and all involved resources locked until the token returns to p/sub i/, although the deadlock was already detected when the probe returned to p/sub i/. This paper proposes the idea of barriers to allow the deadlock to be resolved without waiting for the token to return to p/sub i/, thereby reducing the average deadlock persistence time considerably.

We propose knockout switch-based multistage interconnection networks (KSMINs) for fast packet switching, combining the well-known knockout switch and the concept of multistage interconnection networks. The main objective is to reduce the severe pin requirements of large knockout switches through a phased address filtering. We present an approximate Markov-chain model of KSMINs to study the performance of KSMINs with different numbers of address-filtering phases. The model is shown to be accurate within 5% for all the cases considered and within 20% for the meaningful cases of the buffer sizes /spl ges/4. For the (256/spl times/256) KSMIN, two-phase address filtering based on the (16/spl times/16) knockout switches is shown to perform very closely to the single-stage knockout switch for a reduced hardware cost.>

The knockout switch is a nonblocking, high-performance switch suitable for broadband packet switching. It allows packet losses, but the probability of a packet loss can be kept extremely small in a cost-effective way. The performance of the knockout switch was analyzed under uniform traffic. In this paper, we present a new, more general analytic model of the knockout switch, which enables us to evaluate the knockout switch under nonuniform traffic. The new model also incorporates the effects of a concentrator and a shared buffer on the packet loss probability. Numerical results for nonuniform traffic patterns of interest are presented.>

Signature files have been studied extensively, as an access method for textual databases. Many approaches have been proposed for searching signatures files efficiently. However, different methods make different assumptions and use different performance measures, making it difficult to compare their performance. In this paper, we study three basic methods proposed in the literature, namely, the indexed descriptor file, the two-level superimposed coding scheme, and the partitioned signature file approach. The contribution of this paper is two-fold. First, we present a uniform analytical performance model so that the methods can be compared fairly and consistently. The analysis shows that the two-level superimposed coding scheme, if stored in a transposed file, has the best performance. Second, we extend the two-level superimposed coding method into a multilevel superimposed coding method, we obtain the optimal number of levels for the multilevel method and show that for databases with reasonable size the optimal value is much larger than 2, which is assumed in the two-level method. The accuracy of the analytical formula is demonstrated by simulation.>

Buffered banyan networks are highly vulnerable to nonuniform traffic, due to the path sharing as well as the existence of only a single path per network input-output pair. Improving on an earlier packet distribution network which is a banyan network itself, a single-stage packet-scattering hardware, called the pseudo-randomizer (PR), is proposed. The PR-banyan, the PR followed by a buffered banyan, is analyzed under nonuniform traffic, and is shown to be highly effective under nonuniform traffic. The analytic results are shown to match the simulation results very closely.>

Existing packet combining schemes, implemented either by hardware or software, developed for hot-spot congestion-control in multiprocessors are not applicable for use in telecommunication systems. The authors propose a hot-spot prevention scheme which exploits the structural characteristics of buffered delta networks to regulate the traffic. This scheme prevents the tree saturation by controlling the flow of the packets into the network and ensures that the hot-spot traffic can be supported with little degradation to the throughput of the uniform traffic, even when more than one hot-spot exists. The scheme retains all the desirable properties, including packet order preserving, of buffered delta networks, and is shown by simulations to be highly effective under either light or heavy hot-spot traffic. Since no a priori knowledge of the traffic patterns is required, the proposed scheme can be applied equally well to buffered delta networks in multiprocessors and telecommunication systems.>

This paper presents a new analytic model for buffered Banyan networks. The new model is the most general one in the current literature, and allows the traffic pattern, the buffer size, and the switch size as input parameters among other things. The main motivation of the development of the new model was to provide an analytical tool to evaluate the performances of buffered Banyan networks under nonuniform traffic patterns, which mostly remained unknown except for some very limited cases. With the new model, we measured network performances for several important memory access patterns occurring in the parallel loop execution in multiprocessors. The performance results and the implications of the results on data storage schemes are discussed.