Zhisheng NIU Yoshitaka TAKAHASHI Noboru ENDO
We propose a finite-capacity single-vacation model, with close-down/setup times and a Markovian arrival process (MAP), for SVC-based IP-over-ATM networks. This model considers the SVC processing overhead and the bursty nature of IP packet arrivals. Specifically, the setup time corresponds to the SVC setup time and the vacation time corresponds to the SVC release time, while the close-down time corresponds to the SVC timeout. The MAP is a versatile point process by which typical bursty arrival processes like the IPP (interrupted Poisson process) or the MMPP (Markov modulated Poisson process) is treated as a special case. The approach we take here is the supplementary variable technique. Compared with the embedded Markov chain approach, it is more straightforward to obtain the steady-state probabilities at an arbitrary instant and the practical performance measures such as packet loss probability, packet delay time, and SVC setup rate. For the purpose of optimal design of the SVC-based IP-over-ATM networks, we also propose and derive a new performance measure called the SVC utilization ratio. Numerical results show the sensitivity of these performance measures to the SVC timeout period as well as to the burstiness of the input process.
Katsuhiko SEO Hisao KOIZUMI Barry SHACKLEFORD Masashi MORI Takashi KUSUHARA Hirotaka KIMURA Fumio SUZUKI
This paper proposes a top-down co-verification approach in the design of embedded systems composed of both hardware and software, for multimedia applications. In order to realize the optimized embedded system in cost, performance, power consumption and flexibility, hardware/software co-design becomes to be essential. In this top-down co-design flow, a target design is verified at three different levels: (1) algorithmic, (2) implementation, and (3) experimental. We have developed a methodology of top-down co-verification, which consists of the system level simulation at the algorithmic level, two type of co-simulations at the implementation level and the co-emulation at the experimental level. We have realized an environment optimized for verification performance by employing verification models appropriate to each verification stage and an efficient top-down environment by introducing the component logical bus architecture as the interface between hardware and software. Through actual application to a image compression and expansion system, the possibility of efficient co-verification was demonstrated.
In a secure partially blind signature scheme, the signer assures that the blind signatures issued by him contains the information he desires. The techniques make it possible to minimize the unlimited growth of the bank's database which storing all spent electronic cash in an anonymous electronic cash system. In this paper we propose an efficient partially blind signature scheme for electronic cash. In our scheme, only several modular additions and modular multiplications are required for a signature requester to obtain and verify a signature. It turns out that the proposed scheme is suitable for mobile clients and smart-card applications because no time-consuming computations are required, such as modular exponentiation and inverse computations. Comparing with the existing blind signature schemes proposed in the literatures, our method reduces the amount of computations for signature requesters by almost 98%.
We introduce a concept of regularization into Genetic Algorithms (GAs). Conventional GAs include no explicit regularizing operations. However, the regularization is very effective in solving ill-posed problems. So, we propose a method of regularization to apply GAs to ill-posed problems. This regularization is a kind of consensus operation among neighboring individuals in GAs, and plays the role of `smoothing the solution. ' Our method is based on the evaluation of macroscopic fitness, which is a new fitness criterion. Conventional fitness of an individual in GAs is defined only from the phenotype of the individual, whereas the macroscopic fitness of an individual is evaluated from the phenotypes of the individual and its neighbors. We tested our regularizing operation by means of experiments with an elastic image mapping problem, and showed the effectiveness of the regularization.
Cheng-Shong WU Jin-Chyang JIAU Kim-Joan CHEN
Cell delay variation (CDV) has been considered as an important performance measure due to the stringent timing requirement for video and multimedia services. In this paper we address the problem of CDV performance guarantee in virtual path (VP)-based ATM multiplexing. We propose a rate-based and non-work-conserving scheduling algorithm, called interleaved round robin (IRR), for serving traffic streams among VPs into the outgoing link. Through our performance analysis, the proposed scheme is capable of providing upper and lower bounds on the inter-visit time (IVT) for each VP, where the difference between the upper bound and the lower bound is simply dependent upon the number of multiplexed VPs. The distribution of VP IVT scheduled by an IRR server can also be well approximated using a random incidence technique. In addition to the VP-level CDV performance, we further examine the virtual connection (VC)-level CDV incurred within a multi-stage network through simulation study. The simulation results show that the IRR server can provide traffic regulation and smoothness at each network node. Moreover, the CDV distribution of a tagged VC is insensitive to the source traffic characteristic, node location, and the hop count traversed in the network.
This paper investigates the relations between the computational complexity and the restrictions for several problems that determine whether a given graph with edge costs and edge lengths has a spanning subgraph with such restrictions as the diameter, the connectivity, and the NA-distance and the NA-(edge)-connectivity proposed and investigated in [1]-[5]. The NA-distance and the NA-(edge)-connectivity are the measures for the distance and the connectivity between a vertex and a vertex subset (area). In this paper we prove that the minimum diameter spanning subgraph problem considering the restrictions of the diameter and the sum of edge costs is NP-complete even if the following restrictions are satisfied: all edge costs and all edge lengths are equal to one, and the upper bound of the diameter is restricted to four. Next, we prove that the minimum NA-distance spanning subgraph problem considering the restrictions of the NA-distances and the sum of edge costs is NP-complete even if the following conditions are satisfied: all edge costs and all edge lengths are equal to one, the upper bound of the NA-distance is restricted to four, each area is composed of a vertex, and the number of areas is restricted to two. Finally, we investigate the preserving NA-distance and NA-edge-connectivity spanning subgraph problem considering the preservations of the NA-distances and the NA-edge-connectivity and the restrictions of the sum of edge costs, and prove that a sparse spanning subgraph can be constructed in polynomial time if all edge costs are equal to one.
We present techniques to implement fair-sharing on both link bandwidth and buffer space in a switch or router. Together they possess the following merits: 1. solving the counter-overflow problem; 2. avoiding the "credit" accumulation issue; 3. integrating bandwidth allocation with buffer management. The simplicity of this method makes it a viable candidate for implementational use on switches and routers.
Tetsuya MATSUMURA Hiroshi SEGAWA Satoshi KUMAKI Yoshinori MATSUURA Atsuo HANAMI Kazuya ISHIHARA Shin-ichi NAKAGAWA Tadashi KASEZAWA Yoshihide AJIOKA Atsushi MAEDA Masahiko YOSHIMOTO Tadashi SUMI
This paper describes a chip set architecture and its implementation for programmable MPEG2 MP@ML (main profile at main level) video encoder. The chip set features a functional partitioning architecture based on the MPEG2 layer structure. Using this partitioning scheme, an optimized system configuration with double bus structure is proposed. In addition, a hybrid architecture with dual video-oriented on-chip RISC processors and dedicated hardware and a hierarchical pipeline scheme covering all layers are newly introduced to realize flexibility. Also, effective motion estimation is achieved by a scalable solution for high picture quality. Adopting these features, three kinds of VLSI have been developed using 0. 5 micron double metal CMOS technology. The chip set consists of a controller-LSI (C-LSI), a macroblock level pixel processor-LSI (P-LSI) and a motion estimation-LSI (ME-LSI). The chip set combined with synchronous DRAMs (SDRAM) supports all the layer processing including rate-control and realizes real-time encoding for ITU-R-601 resolution video (720480 pixels at 30 frames/s) with glue less logic. The exhaustive motion estimation capability is scalable up to 63. 5 and 15. 5 in the horizontal and vertical directions respectively. This chip set solution realizes a low cost MPEG2 video encoder system with excellent video quality on a single PC extension board. The evaluation system and application development environment is also introduced.
Woo-Yong CHOI Chi-Hyuck JUN Jae Joon SUH
We propose a new approach to the exact performance analysis of a shared buffer ATM multiplexer, which is loaded with mixed correlated and uncorrelated traffic sources. We obtain the joint steady-state probabilities of both states of the input process and the buffer using a one-dimensional Markov chain. From these probabilities we calculate the loss probabilities and the average delays of the correlated and the uncorrelated traffic sources.
In live multimedia applications with multiple videos, it is necessary to develop an efficient mechanism of multiplexing several MPEG video streams into a single stream and transmitting it over network without wasting excessive bandwidth. In this paper, we present an efficient multiplexing and traffic smoothing scheme for multiple variable bit rate (VBR) MPEG video streams in live video applications with finite buffer sizes. First, we describe the constraints imposed by the allowable delay bound for each elementary stream and by the multiplexer/receiver buffer sizes. Based on these constraints, a new multiplexing and traffic smoothing scheme is designed in such a way as to smooth maximally the multiplexed transmission rate by exploiting temporal and spatial averaging effects, while avoiding the buffer overflow and underflow. Through computer experiments based on an MPEG-coded video trace of Star-wars, it is shown that the proposed scheme significantly reduces the peak rate, coefficient of variation, and effective bandwidth of the multiplexed transmission rate.
Despite the fact that the necessity of FDT (formal description techniques) had been emphasized, many approaches to verifying feature interactions were insufficient. This paper proposes formal definitions for feature interactions which can occur when telecommunication services specified independently are operated in parallel. Seven types of feature interactions are defined formally.
Ichiro KOIWA Yukihisa OKADA Juro MITA
Sr0. 7Bi2. 3Ta2O9(SBT) films are drawing attention as fatigue-free materials. We prepared an SBT film containing discontinuous crystals in the Bi-layered compound using a misted deposition method. In comparison to films prepared by the spin-on method, leakage current was low and spontaneous polarization is high but saturation performance was low. The low saturation performance seems attributable to the inclusion of discontinuous crystals in the Bi-layered compound, while the low leakage current may be explained by the films smaller, denser particles, which form a film without voids, resulting in higher uniformity. The misted deposition method has advantages of finer grain size and higher uniformity.
Michiko KURODA Hideyoshi ISOBE Hiroyuki KASAI
A new numerical approach for the analysis of electromagnetic scattering from a body moving in an arbitrary direction is described. A time dependent grid generation is applied to solve these problems. We are treating this method for a quasi-stationary field. Some numerical results are compared with the exact ones and excellent agreement between them is obtained.
Silva et al. has suggested a criterion based on incidence matrix to verify if a given extended free choice net has a live and bounded marking. This paper shows that this criterion is a necessary and sufficient condition that a given net is a state machine allocatable (SMA) net. This result gives a polynomial algorithm to verify SMA net.
Tadashi MATSUMOTO Yasushi MIYANO
A formal necessary and sufficient condition on the general Petri net reachability problem is presented by eliminating all spurious solutions among known nonnegative integer solutions of state equation and unifying all the causes of those spurious solutions into a maximal-strongly-connected and siphon-and-trap subnet Nw. This result is based on the decomposition of a given net (N, Mo) with Md and the concepts of "no immature siphon at the reduced initial marking Mwo" and "no immature trap at the reduced end marking Mwd" on Nw which are both extended from "no token-free siphon at the initial marking Mo" and "no token-free trap at the end marking Md" on N, respectively, which have been both effectively, explicitly or implicitly, used in the well-known fundamental and simple subclasses.
Isao NAKANISHI Yoshihisa HAMAHASHI Yoshio ITOH Yutaka FUKUI
In this paper, we propose a new structure of the frequency domain adaptive filter (FDAF). The proposed structure is based on the modified DFT pair which consists of the FIR filters, so that un-delayed output signal can be obtained with stable convergence and without accumulated error which are problems for the conventional FDAFs. The convergence performance of the proposed FDAF is examined through the computer simulations in the adaptive line enhancer (ALE) comparing with the conventional FDAF and the DCT domain adaptive filter. Furthermore, in order to improve the error performance of the FDAF, we propose a composite algorithm which consists of the normalized step size algorithm for fast convergence and the variable step size one for small estimation error. The advantage of the proposed algorithm is also confirmed through simulations in the ALE. Finally, we propose a reduction method of the computational complexity of the proposed FDAF. The proposed method is to utilize a part of the FFT flow-graph, so that the computational complexity is reduced to O(N log N).
Toshihiko ANDO Kaoru TAKAHASHI Yasushi KATO Norio SHIRATORI
Process algebras with name passing have been proposed for concurrent mobile processes. They can be suitable to describe dynamical changes of connections among processes. To describe mobile communication or mobile computing systems, however, it is necessary to consider locations at which processes run. We propose a description method to design mobile communication systems using a concurrent calculus in this paper. The concept of a field is introduced to model locality of communication. An extension of π-calculus with a field is proposed. The extension does not include locality represented by a field while most related works treat locality within their languages. A field is given when behavior of a target system is verified in a particular environment. The aim of the extension is to verify and to test connectivity between processes under various geographical constraints. This method could be design-oriented in this context. Equivalence relations with/without location in this calculus are also discussed.
Tetsuya OSAKA Sachiko ONO Akira SAKAKIBARA Ichiro KOIWA
Using transmission electron microscopy (TEM), we studied structural defects in a Sr0. 7Bi2. 3Ta2O9 (SBT) thin film to be used for ferroelectric memory devices. We examined the effects of the substrate, crystal continuity, and dislocations in crystals as major causes of defects. For this study, we used an SBT thin film grown from an alkoxide solution. Since crystal growth was hardly influenced by the substrate, the substrate had little influence on the occurrence of defects resulted in misfit of lattice constant. Regions of partially low crystal continuity were observed in the SBT thin film. In these regions, the orientation was still uniform, but the continuity of the crystal grain was low because of the defects. In addition, variation in contrast was observed in the crystals, however, no obvious variation in chemical composition was found in this region of varying contrast. Therefore, the contrast variation is considered to be attributed to the dislocation. Such a dislocation was found to be occurred in the direction of the (2010) plane in many instances. The defects in the SBT film were also confirmed by the TEM observation.
Toshiyuki KAWASAKI Yoshikazu AKIYAMA Shunsuke FUJITA Shiro SATOH
The metal/ferroelectric material/metal/oxide insulating material/Si substrates (MFMIS) structure was realized by using Pb(Zr0. 4Ti0. 6)O3 (PZT) thin film. PZT(330 nm thick) thin film was sandwiched between the upper electrode of Ti/Pt-Rh (about 380 nm thick and 123 microns in diameter) and the lower electrode of Pt-Rh/Ti (about 380 nm thick and 378 microns in diameter). The MFM structures mentioned above were prepared on metal oxide semiconductor (MOS structures). Pt-Rh and Ti lower electrodes were directly deposited on a poly-Si MOS electrode with sputtering, and PZT layer was prepared using the sol-gel method. In order to maximize induced charge density in the MOS gate, diameters of the upper and the lower electrodes were adjusted, and the MFM area-to-MOS area ratio was optimized. By using the area ratio of 0. 11 a memory window of 2. 4 V was obtained.
Akira NAKA Toshiya MATSUDA Shigeru SAITO
RZ signal transmission in an anomalous region with periodic dispersion compensation is examined by a straight-line experiment in terms of the compensation ratio, the signal power, and the pulse width. The optimum condition enables single-channel 20-Gbit/s RZ signal and two-WDM-channel 20-Gbit/s signals (40-Gbit/s in total) to be transmitted over 5,520 km and 2,160 km, respectively. Numerical simulations with the assistance of a basic theory enables analysis of the experimental results. It is shown that the balance between the waveform distortion and the remaining Gordon-Haus jitter determines the optimum conditions to achieve the longest transmission distance. Excess dispersion compensation results in waveform distortion, while insufficient compensation causes a greater amount of remaining jitter. Moreover, spectrum deformation during propagation is experimentally and numerically clarified to have a large effect on the transmission performance, especially for WDM transmission.