Jacir Luiz BORDIM Jiangtao CUI Naohiro ISHII Koji NAKANO
A radio network is a distributed system with no central shared resource, consisting of n stations each equipped with a radio transceiver. One of the most important parameters to evaluate protocols in the radio networks is the number of awake time slots in which each individual station sends/receives a data packet. We are interested in devising energy-efficient initialization protocols in the single-hop radio network (RN, for short) that assign unique IDs in the range [1,n] to the n stations using few awake time slots. It is known that the RN can be initialized in O(log log n) awake time slots, with high probability, if every station knows the number n of stations in the RN. Also, it has been shown that the RN can be initialized in O(log n) awake time slots even if no station knows n. However, it has been open whether the initialization can be performed in O(log log n) awake time slots when no station knows n. Our main contribution is to provide the breakthrough: we show that even if no station knows n, the RN can be initialized by our protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log log n) time slots. We then go on to design an initialization protocol for the k-channel RN that terminates, with high probability, in O(n/k + (log n)2) time slots with no station being awake for more than O(log log n) time slots.
Mitiko MIURA-MATTAUSCH Hiroaki UENO Hans Juergen MATTAUSCH Shigetaka KUMASHIRO Tetsuya YAMAGUCHI Kyoji YAMASHITA Noriaki NAKAYAMA
The urgent tasks of MOSFET modeling for circuit simulation are easy adaptation to new physical phenomena arising for advancing technologies, and, of course, sufficient simulation accuracy. Approaches currently being pursued for developing such MOSFET models are summarized. Their capabilities for accomplishing these tasks as well as the important remaining problems are discussed. Main focus is given on the model HiSIM, the first commonly available model based on the drift-diffusion approximation developed for 0.10 µm MOSFET technology node.
System specifications should be refined to meet stakeholders' requirements as much as possible, because the first specification does not satisfy all stakeholders in general. This paper presents a procedure to refine behavioral specification to satisfy stakeholders. Non-functional requirements are used for checking stakeholders' satisfaction. With this procedure, stakeholder-dissatisfaction can be reduced and new possibilities to satisfy or dissatisfy other stakeholders can be found, since a modification to cancel dissatisfaction can sometimes influence the satisfaction of the others.
Shinichi NODA Nozomu TOGAWA Masao YANAGISAWA Tatsuo OHTSUKI
At high-level synthesis for system VLSIs, their power consumption is efficiently reduced by applying gated clocks to them. Since using gated clocks causes the reduction of power consumption and the increase of area/delay, estimating trade-off between power and area/delay by applying gated clocks is very important. In this paper, we discuss the amount of variance of area, delay and power by applying gated clocks. We propose a simple gate-level circuit model and estimation equations. We vary parameters in our proposed circuit model, and evaluate power consumption by back-annotating gate-level simulation results to the original circuit. This paper also proposes a conditional expression for applying gated clocks. The expression shows whether or not we can reduce power consumption by applying gated clocks. We confirm the accuracy of proposed estimation equations by experiments.
Jong-Youl PARK Dong-Ik LEE Hyung-Hyo LEE Joong-Gil PARK
This paper deals with security issues in a mobile agent system, especially protecting agent data from malicious servers. For this purpose, one-time key generation system, OKGS in short, is proposed. In OKGS, we integrate notions of an one-way hash function and a coupler. A one-way function plays a major role in ensuring confidentiality and integrity of agent data. And the notion of a coupler is used to establish inter-relationship among consecutive encryption keys for agent data, i.e,. all agent keys form a unidirectional chain. With these two features of OKGS, therefore, only the agent owner, who creates the agent bearing data, can decrypt and protect all agent data which are gathered in its itinerary.
We have developed and demonstrated a novel technique for electrical inspection and electrical failure analysis, which can detect open, high-resistance, and short circuits without the need for electrical contact with the outside of the LSI chip or the board on which the LSI chip is mounted. The basic idea of the technique is the detection of the magnetic field produced by OBIC (optical beam induced current) or photo current. A DC-SQUID (superconducting quantum interference device) magnetometer is used to detect the magnetic field. This scanning laser-SQUID microscopy ("laser-SQUID" for short) has a spatial resolution of about 1.3 µm. It can be used to distinguish defective chips before bonding pad patterning or after bonding without pin-selection. It can localize any defective site in the chip to within a few square microns.
Keiji ENPUKU Daishi TOKIMIZU Daisuke KURODA Shintaro HIJIYA
Thermally activated magnetic-flux entry into a pickup coil through a flux dam in high Tc superconducting quantum interference device (SQUID) is studied. The behavior of this thermal activation is analyzed in terms of the circulating current flowing in the pickup coil. It is shown that the thermal activation can be prevented when the circulating current becomes much below a critical current of the flux dam. It is also shown that we need a long waiting time in order to realize this situation since the circulating current logarithmically decays with time in the case of the thermal activation. The relationship between the thermal activation and the circulating current is qualitatively confirmed with the experiment. We also show a method in order to forcibly reduce the circulating current instead of the thermal activation. In this case, we can prevent the thermal activation without the long waiting time.
In the field of computer graphics (CG), some adaptive methods have been proposed in order to make CG images more real in relatively low computational cost. As one of such adaptive methods, in this paper, an adaptive method will be proposed for detection of edges and approximation of surfaces in the use of the so-called automatic differentiation. In the proposed method a CG image with high quality can be generated in suitable computational cost. In this paper, three cases will be considered. The first is an adaptive distributed ray tracing which can adaptively generate anti-aliased CG images in suitable computational cost. The second is a high quality triangular meshing, which guarantees accuracy of the generated meshes according to shape of given surface in suitable computational cost. The last case is used in the so-called radiosity method.
Tristan KREMP Alexander KILLI Andreas RIEDER Wolfgang FREUDE
With the emerging technology of photonic networks, careful design becomes necessary to make most of the already installed fibre capacity. Appropriate numerical tools are readily available. Usually, these are based on the split-step Fourier method (SSFM), employing the fast Fourier transform (FFT). With N discretization points, the complexity of the SSFM is O(N log2N). For real-world wavelength division multiplexing (WDM) systems, the simulation time can be of the order of days, so any speed improvement would be most welcome. We show that the SSFM is a special case of the so-called collocation method with harmonic basis functions. However, for modelling nonlinear optical waveguides, various other basis function systems offer significant advantages. For calculating the propagation of single soliton-like impulses, a problem-adapted Gauss-Hermite basis leads to a strongly reduced computation time compared to the SSFM . Further, using a basis function system constructed from a scaling function, which generates a compactly supported wavelet, we developed a new and flexible split-step wavelet collocation method (SSWCM). This technique is independent of the propagating impulse shapes, and provides a complexity of the order O(N) for a fixed accuracy. For a typical modelling situation with up to 64 WDM channels, the SSWCM leads to significantly shorter computation times than the standard SSFM.
The power supply voltage of LSI has been lowered due to system requirements for low power dissipation. An on-chip power-on reset pulse generator (POR-PG) is used to determine the initial state of the memory devices of the system LSI. The requirement for the POR-PG is strict for lower power supply voltage because noise margin is smaller relatively. This paper describes a POR-PG for low power voltage supply (Vdd) which overcomes these problems. Hardware measurement proves improved pulse height relative to various power-on profiles (slope, rise time etc.) and fluctuations of temperature and process. Further, the design provides robust noise immunity against voltage fluctuations on the power supply line. The circuit is implemented within a small area (115 µm 345 µm) in the input/output buffer area of a micro-processor and hard-disk controller integrated LSI with 0.25-µm four-layer-metal CMOS technology.
Raghuvel Subramaniam BHUVANESWARAN Jacir Luiz BORDIM Jiangtao CUI Naohiro ISHII Koji NAKANO
A Wireless Sensor Network (WSN, for short) is a distributed system consisting of n sensor nodes and a base station. In this paper, we propose an energy-efficient protocol to initialize the sensor nodes in a WSN, that is, to assign a unique ID to each sensor node. We show that if an upper bound u on the number n of sensor nodes is known beforehand, for any f 1 and any small µ (0<µ<1), a WSN without collision detection capability can be initialized in O((log (1/µ) + log f)u1+µ) time slots, with probability exceeding 1-(1/f), with no sensor node being awake for more than O(log (1/µ)+ log f) time slots.
Deukjo HONG Jaechul SUNG Shiho MORIAI Sangjin LEE Jongin LIM
In this paper, we discuss the impossible differential cryptanalysis for the block cipher Zodiac. The main design principles of Zodiac include simplicity and efficiency. However, the diffusion layer in its round function is too simple to offer enough security. The impossible differential cryptanalysis exploits such weakness in Zodiac. Our attack using a 14-round impossible characteristic derives the 128-bit master key of the full 16-round Zodiac faster than the exhaustive search. The efficiency of the attack compared with exhaustive search increases as the key size increases.
We propose a new and fast full search (FS) motion estimation algorithm for video coding. The computational reduction comes from sequential rejection of impossible candidates with derived formula and subblock norms. Our algorithm reduces more the computations than the recent fast full search (FS) motion estimation algorithms.
Masayuki KANDA Tsutomu MATSUMOTO
This paper studies security of Feistel ciphers with SPN round function against differential cryptanalysis, linear cryptanalysis, and truncated differential cryptanalysis from the "designer's standpoint." In estimating the security, we use the upper bounds of differential characteristic probability, linear characteristic probability and truncated differential probability, respectively. They are useful to design practically secure ciphers against these cryptanalyses. Firstly, we consider the minimum numbers of differential and linear active s-boxes. They provide the upper bounds of differential and linear characteristic probability, which show the security of ciphers constructed by s-boxes against differential and linear cryptanalysis. We clarify the (lower bounds of) minimum numbers of differential and linear active s-boxes in some consecutive rounds of the Feistel ciphers by using differential and linear branch numbers, Pd, Pl, respectively. Secondly, we discuss the following items on truncated differential probability from the designer's standpoint, and show how the following items affect the upper bound of truncated differential probability; (a) truncated differential probability of effective active-s-box, (b) XOR cancellation probability, and (c) effect of auxiliary functions. Finally, we revise Matsui's algorithm using the above discussion in order to evaluate the upper bound of truncated differential probability, since we consider the upper bound of truncated differential probability as well as that of differential and linear probability.
Yoshiaki HORI Takeshi IKENAGA Yuji OIE
We have focused on the RIO queueing mechanism in statistical bandwidth allocation service, which uses AF-PHB. We have studied the parameterization of RIO to achieve both high throughput and low delay. We were able to parameterize RIO for that purpose in terms of both minth and maxp used in dropping OUT packets. Furthermore, we have also examined the parameterization regarding EWMA (Exponential Weighted Moving Average), i.e., weight factor wqout, and have shown that dropping OUT packets should depend upon the queue length without much delay unlike in RED. From our simulation results, we could see that our parameterization provided high throughput performance and also limited the queue length in a narrow range more effectively.
Yuan-Sun CHU Ruey-Bin YANG Cheng-Shong WU Ming-Cheng LIANG
In a shared buffer packet switch, a good buffer management scheme is needed to reduce the overall packet loss probability and improve the fairness between different users. In this paper, a novel buffer control scheme called partial sharing and partial partitioning (PSPP) is proposed. The PSPP is an adaptive scheme that can be dynamically adjusted to the changing traffic conditions while simple to implement. The key idea of the PSPP is that part of the buffer space, proportional to the number of inactive output ports, is reserved for sharing between inactive output ports. This portion of buffer is called PS buffer. The residual buffer space, called PP buffer, is partitioned and distributed to active output ports equally. From the analysis results, we only need to reserve a small amount of PS buffer space to get good performance for the entire system. Computer simulation shows the PSPP control is very robust and very close to the performance of pushout (PO) buffer management scheme which is a scheme considered as optimal in terms of fairness and total loss ratio while too complicated for implementation.
OFDM modulation has attracted attention for fourth-generation mobile communication systems and high-speed wireless LANs. However, it has a very serious problem of large peak power. PTS (partial transmit sequences) has been proposed as one solution to this problem. In PTS, the OFDM subcarriers are divided into several clusters, and the phase of each cluster is rotated by a complex weight to minimize the PAPR (peak-to-average power ratio). However, the weight of the phase rotation must be sent to the mobile terminal by using a side information channel. In this paper, we propose two weight estimation methods at the receiver to avoid weight transmission in side information channels. The first method uses pilot signals, while the second is a blind estimation method that changes the weight pattern. We evaluate the performance of these methods by computer simulation.
Kaori KOBAYASHI Tsuyoshi KATAYAMA
For several years, more and more people are joining the Internet and various kind of packets (so called transaction-, block-, and stream-types) have been transmitted in the same network, so that poor network conditions cause loss of the stream-type data packets, such as voices, which request smaller transmission delay time than others. We consider a switching node (router) in a network as an N-series M/G/1-type queueing model and have mainly evaluated the fluctuation of packet delay time and end-to-end delay time, using the two moments matching method with initial value, then define the delay jitter D of a network which consists of jointed N switching nodes. It is clarified that this network is not suitable for voice packets transmission media without measures.
An algorithm based on the wavelet transform (WT) was developed to analyze the QRS complex in a three-dimensional magnetocardiogram (3-D MCG) recorded from 3 normal subjects and 1 patient with anterior myocardial infarction (MI). By using a wavelet equivalent filter constructed with the WT algorithm, the high frequency components of the QRS complex related to the late fields (LF) were detected for the patient with anterior MI at different scale. We quantified the high frequency components of the QRS complex by calculating root-mean-square (RMS) value at different scale. The LF mainly existed in the frequency band of about 35.5 to 110.5 Hz with the amplitude of about 0.1 to 0.4 pT for Bx, By, and Bz components. In order to discuss the activities of the heart between the normal subject and the patient with anterior MI, we have also evaluated the spatial energy distribution (SED) of the QRS complex by displaying isoenergy contour maps at different scale. Being different from the normal subject, the patient with anterior MI represented different the pattern of the SED in various frequency band for the ST segment of the QRS complex of Bx, By, and Bz components. It is efficient to use the WT algorithm for analyzing the QRS complex in the 3-D MCG.
Chun-Liang LEE Chi-Wei CHEN Yaw-Chung CHEN
The differentiated services (Diffserv) architecture is a potential solution for providing quality of service (QoS) on the Internet. Most existing studies focus on providing service differentiation among few service classes. In this paper, we propose an approach which can achieve per-flow weighted fair rate allocation in a differentiated services network. Following the design philosophy of the Diffserv model, in the proposed approach core routers do not need to keep per-flow information. An edge router adjusts the transmission rate of a flow based on the feedback carried on control packets, which are inserted by the ingress edge router and returned by the egress edge router. Core routers periodically estimate the fair share rate of each virtual flow and mark the results in control packets. We use both simulations and analysis to evaluate the performance of the proposed approach. The analytical results show that our approach allows a system to converge to weighted fair rate allocations in limited time. Through the simulation results, we can further validate the analytical results, and demonstrate that better throughput can be achieved.