Combined input-crosspoint buffered (CICB) switches relax arbitration timing and provide high-performance switching for packet switches with high-speed ports. It has been shown that these switches, with one-cell crosspoint buffer and round-robin arbitration at input and output ports, provide 100% throughput under uniform traffic. However, under admissible traffic patterns with nonuniform distributions, only weight-based selection schemes are reported to provide high throughput. This paper proposes a round-robin based arbitration scheme for a CICB packet switch that provides 100% throughput for several admissible traffic patterns, including those with uniform and nonuniform distributions, using one-cell crosspoint buffers and no speedup. The presented scheme uses adaptable-size frames, where the frame size is determined by the traffic load.
Makoto TAKIZAWA Hiroto AIDA Masato SAITO Yoshito TOBE Hideyuki TOKUDA
In this paper, we present a novel forwarding scheme to enhance communication stability based on geographic routing in mobile ad hoc networks, which is called "Position-based Heuristic Forwarding" (PHF). For alternative solutions to traditional ad hoc routings, many geographic routing algorithms have been proposed. Most of the existing routings impose a certain restriction, planarity, on the graph structure of network for delivering messages to destination definitely. PHF achieves the guaranteed packet delivery over Unit Disk Graph, which is more widely employed graph model for the study of ad hoc networks. Accordingly, to eliminate the restriction of the routing algorithms enhances the probability to deliver messages successfully in networks with high nodes' mobility rate. In the simulation of PHF, we have evaluated the performance comparisons between PHF and its related work, Greedy Perimeter Stateless Routing (GPSR) and Dynamic Source Routing (DSR), which are the prominent geographic and conventional topology-based routing protocols, respectively. The results show that PHF provides higher packet delivery success rate indicating better communication stability and equal or less overhead than these work.
Multi-context FPGAs allow very quick reconfiguration by storing multiple configuration data at the same time. While testing for FPGAs with single-context memories has already been studied by many researchers, testing for multi-context FPGAs has not been proposed yet. This paper presents an architecture of testable multi-context FPGAs. In the proposed multi-context FPGA, configuration data stored in a context can be copied into another context. This paper also shows testing of the proposed multi-context FPGA. The proposed testing uses the testing for the traditional FPGAs with single-context. The testing is capable of detecting single stuck-at faults and single open faults which affect normal operations. The number of test configurations for the proposed testing is at most two more than that for the testing of FPGAs with single-context memories. The area overhead of the proposed architecture is 7% and 4% of the area of a multi-context FPGA without the proposed architecture when the number of contexts in a configuration memory is 8 and 16, respectively.
This letter presents a new stable clustering architecture to reduce the number of re-clustering in MANET. Since some existing stable clustering schemes based on measured metric have certain deficiency in negative effect caused by nodes moving fast or causing ping pong effect, we introduce average connection time as major parameter to form as well as maintain cluster structure over the entire networks. From simulation results it is clear that average connection time is more adequate parameter for stable cluster architecture than other measured factors, resulting in fewer number of cluster changes than previous schemes.
Wim HENDRIX Jan DOUTRELOIGNE Andre VAN CALSTER
Bi-stable displays form the foundation of a novel and attractive LCD technology. From now on, images can be maintained on the LCD after driving voltages have been withdrawn from the electrodes. In low frame-rate applications such as e-books, e-labels, smartcards etc., this offers a major improvement in power consumption and battery life. However, bi-stable displays require high driving voltages and complex waveforms. Furthermore, the nature of some applications doesn't allow the use of relatively large passive components. This rules out more traditional approaches for high-voltage generation with external coils or capacitors. This paper describes the design of completely integrated and programmable high-voltage generators capable of generating output voltages up to 50 V out of a 3 V supply voltage. Features like 8-bit output voltage programmability and stabilisation were implemented to make this type of high-voltage generator suitable for bi-stable display drivers. Design aspects and simulation results are discussed, as well as measurements on prototype generators implemented in the 0.7 µm 100 V I2T100 technology from AMI Semiconductor.
Tetsuya MATSUNO Nobuaki TOMINAGA Koji ARIZONO Taisen IGUCHI Yuji KOHARA
Activity patterns of metabolic subnetworks, each of which can be regarded as a biological function module, were focused on in order to clarify biological meanings of observed deviation patterns of gene expressions induced by various chemical stimuli. We tried to infer association structures of genes by applying the multivariate statistical method called graphical Gaussian modeling to the gene expression data in a subnetwork-wise manner. It can be expected that the obtained graphical models will provide reasonable relationships between gene expressions and macroscopic biological functions. In this study, the gene expression patterns in nematodes under various conditions (stresses by chemicals such as heavy metals and endocrine disrupters) were observed using DNA microarrays. The graphical models for metabolic subnetworks were obtained from these expression data. The obtained models (independence graph) represent gene association structures of cooperativities of genes. We compared each independence graph with a corresponding metabolic subnetwork. Then we obtained a pattern that is a set of characteristic values for these graphs, and found that the pattern of heavy metals differs considerably from that of endocrine disrupters. This implies that a set of characteristic values of the graphs can representative a macroscopic biological meaning.
To estimate the number of substring matches against string data, count suffix trees (CS-tree) have been used as a kind of alphanumeric histograms. Although the trees are useful for substring count estimation in short data strings (e.g. name or title), they reveal several drawbacks when the target is changed to extremely long strings. First, it becomes too hard or at least slow to build CS-trees, because their origin, the suffix tree, has memory-bottleneck problem with long strings. Secondly, some of CS-tree-node counts are incorrect due to frequent pruning of nodes. Therefore, we propose the count q-gram tree (CQ-tree) as an alphanumeric histogram for long strings. By adopting q-grams (or length-q substrings), CQ-trees can be created fast and correctly within small available memory. Furthermore, we mathematically provide the lower and upper bounds that the count estimation can reach to. To the best of our knowledge, our work is the first one to present such bounds among research activities to estimate the alphanumeric selectivity. Our experimental study shows that the CQ-tree outperforms the CS-tree in terms of the building time and accuracy.
Koichi ITO Masahiko HIRATSUKA Takafumi AOKI Tatsuo HIGUCHI
This paper presents a shortest path search algorithm using a model of excitable reaction-diffusion dynamics. In our previous work, we have proposed a framework of Digital Reaction-Diffusion System (DRDS)--a model of a discrete-time discrete-space reaction-diffusion system useful for nonlinear signal processing tasks. In this paper, we design a special DRDS, called an "excitable DRDS," which emulates excitable reaction-diffusion dynamics and produces traveling waves. We also demonstrate an application of the excitable DRDS to the shortest path search problem defined on two-dimensional (2-D) space with arbitrary boundary conditions.
Shigeaki TAGASHIRA Syuhei SHIRAKAWA Satoshi FUJITA
Content-Addressable Network (CAN) provides a mechanism that could retrieve objects in a P2P network by maintaining indices to those objects in a fully decentralized manner. In the CAN system, index caching is a useful technique for reducing the response time of retrieving objects. The key points of effective caching techniques are to improve cache hit ratio by actively sharing caches distributed over the P2P network with every node and to reduce a maintenance and/or routing overhead for locating the cache of a requested index. In this paper, we propose a new caching technique based on the notion of proxy-type caching techniques which have been widely used in WWW systems. It can achieve active cache sharing by incorporating the concept of proxy caching into the index access mechanism and locate a closer proxy cache of a requested index with a little routing overhead. By the result of simulations, we conclude that it can improve the response time of retrieving indices by 30% compared with conventional caching techniques.
Krishna KANT Amit SAHOO Nrupal JANI
Given the availability of high-speed Ethernet and HW based protocol offload, clustered systems using a commodity network fabric (e.g., TCP/IP over Ethernet) are expected to become more attractive for a range of e-business and data center applications. In this paper, we describe a comprehensive simulation to study the performance of clustered database systems using such a fabric. The simulation model currently supports both TCP and SCTP as the transport protocol and models an Oracle 9i like clustered DBMS running a TPC-C like workload. The model can be used to study a wide variety of issues regarding the performance of clustered DBMS systems including the impact of enhancements to network layers (transport, IP, MAC), QoS mechanisms or latency improvements, and cluster-wide power control issues.
Xiaomeng HUANG Chuang LIN Fengyuan REN
In this letter we examine two transport protocols, HighSpeed TCP [1] and Scalable TCP [2] which are both sender-side varieties of TCP. Based on the fluid flow theory, we develop a general nonlinear model and use gain margin and phase margin to evaluate the stability of a closed-loop system which is composed of a transport protocol and an active queue management scheme. Our results indicate that HSTCP and STCP are stabler than standard TCP when link bandwidth, flow number and round-trip time vary.
We propose a new security class, called plaintext simulatability, defined over the public-key encryption schemes. The notion of plaintext simulatability (denoted PS) is similar to the notion of plaintext awareness (denoted PA) defined in [3], but it is "properly" a weaker security class for public-key encryption. It is known that PA implies the class of CCA2-secure encryption (denoted IND-CCA2) but not vice versa. In most cases, PA is "unnecessarily" strong--In such cases, PA is only used to study that the public-key encryption scheme involved meets IND-CCA2, because it looks much easier to treat the membership of PA than to do "directly" the membership of IND-CCA2. We show that PS also implies IND-CCA2, while preserving such a technical advantage as well as PA. We present two novel CCA2-secure public-key encryption schemes, which should have been provided with more complicated security analyses. One is a random-oracle version of Dolev-Dwork-Naor's encryption scheme [8],[9]. Unlike the original scheme, this construction is efficient. The other is a public-key encryption scheme based on a strong pseudo-random permutation family [16] which provides the optimal ciphertext lengths for verifying the validity of ciphertexts, i.e., (ciphertext size) = (message size) + (randomness size). According to [19], such a construction remains open. Both schemes meet PS but not PA.
In optical burst switching (OBS) networks, the contention of optical bursts is the most serious problem due to the lack of buffers within the networks. Various deflection routing schemes and a routing scheme based on pre-calculated multiple paths have been proposed to resolve the contention. The latter routing scheme can successfully maintain a relatively limited transfer delay of optical bursts. This paper proposes a new decentralized routing scheme based on multiple paths to effectively resolve the contention of optical bursts. In this scheme, each source node splits the traffic load into pre-calculated multiple paths adaptively according to the measured loss rate of the optical bursts transferred through each path. This scheme does not require frequent notification of the measured loss rate because each source node selects one of the multiple paths probabilistically. In the OBS networks, the average transfer delay in the multi-path routing always exceeds that in a single-path routing because alternative paths with a larger transfer delay are also utilized in the multi-path routing. Thus, this paper proposes an adaptive load splitting method in which load splitting ratios for the multiple paths are autonomously adjusted to minimize the average transfer delay based on the condition that the required loss rate of optical bursts is satisfied. The performance of the proposed scheme was evaluated by computer simulation and based on the evaluation results; the ability of the proposed scheme to adjust the load splitting ratios for the multiple paths autonomously and avoid the contention of optical bursts adaptively is clarified even if the traffic load applied to the OBS network changes.
Yasunori ISHIHARA Shuichiro AKO Toru FUJIWARA
Inference attacks mean that a user derives information on the execution results of unauthorized queries from the execution results of authorized queries. Most of the studies on inference attacks so far have focused on only inference of positive information (i.e., what value is the execution result of a given unauthorized query). However, negative information (i.e., what value is never the execution result of a given unauthorized query) is also sensitive in many cases. This paper presents the following results on the security against inference attacks on negative information in object-oriented databases. First, inference of negative information is formalized under a model of object-oriented databases called method schemas. Then, the following two types of security problems are defined: (1) Is a given database instance secure against inference attacks on given negative information? (2) Are all of the database instances of a given database schema secure against inference attacks on given negative information? It is shown that the first problem is decidable in polynomial time in the description size of the database instance while the second one is undecidable. A decidable sufficient condition for any database instance of a given database schema to be secure is also proposed. Finally, it is shown that for a monadic schema (i.e., every method has exactly one parameter), this sufficient condition is also a necessary one.
Chia Yee OOI Thomas CLOUQUEUR Hideo FUJIWARA
This paper introduces τk notation to be used to assess test generation complexity of classes of sequential circuits. Using τk notation, we reconsider and restate the time complexity of test generation for existing classes of acyclic sequential circuits. We also introduce a new DFT method called feedback shift register (FSR) scan design technique, which is extended from the scan design technique. Therefore, for a given sequential circuit, the corresponding FSR scan designed circuit has always equal or lower area overhead and test application time than the corresponding scan designed circuit. Furthermore, we identify some new classes of sequential circuits that contain some cyclic sequential circuits, which are τ-equivalent and τ2-bounded. These classes are the l-length-bounded testable circuits, l-length-bounded validity-identifiable circuits, t-time-bounded testable circuits and t-time-bounded validity-identifiable circuits. In addition, we provide two examples of circuits belonging to these classes, namely counter-cycle finite state machine realizations and state-shiftable finite state machine realizations. Instead of using a DFT method, a given sequential circuit described at the finite state machine (FSM) level can be synthesized using another test methodology called synthesis for testability (SFT) into a circuit that belongs to one of the easily testable classes of cyclic sequential circuits.
Cherng-Chyi HSIAO Ruey Bing HWANG
In this paper, we presented a beam adjustable antenna made up of a slit waveguide and a dielectric slab. In order to change the radiation main-beam angle, we changed the phase constant of the waveguide mode by inserting a dielectric slab for perturbing its field distribution. The direction of radiation main-beam can be steered by dynamically changing the position of the dielectric slab. For the theoretical analysis, the dispersion relation, including the phase and attenuation constants, was determined by solving the transverse resonance equation. An agreement between the theoretical and experimental radiation pattern verifies the beam-steering mechanism. Up to 23beam-steering angle can be achieved using this approach.
Mitsutoshi YAHARA Kuniaki FUJIMOTO Hirofumi SASAKI
In this paper, we propose a voltage controlled oscillator (VCO) with up mode type Miller-integrator. The controlled voltage of this VCO can continuously change 0 V center in the positive and negative bidirection. Also, the relationship between control voltage and oscillating frequency shows the good linearity, and the calculated and the measured values agree well.
A method for fast but yet accurate performance evaluation of processor architecture is mostly desirable in modern processors design. This paper proposes one such method which can measure cycle counts and power consumption of pipelined processors. The method first develops a trace-driven performance simulation model and then employs simulation reuse in simulation of the model. The trace-driven performance modeling is for accuracy in which performance simulation uses the same execution traces as constructed in simulation for functional verification. Fast performance simulation can be achieved in a way that performance for each instruction in the traces is evaluated without evaluation of the instruction itself. Simulation reuse supports simulation speedup by elimination of an evaluation at the current state, which is identical to that at a previous state. The reuse approach is based on the property that application programs, especially multimedia applications, have many iterative loops in general. A performance simulator for pipeline architecture based on the proposed method has been developed through which greater speedup has been made compared with other approaches in performance evaluation.
Seokjin HONG Bongki MOON Sukho LEE
A range top-k query returns the topmost k records in the order set by a measure attribute within a specified region of multi-dimensional data. The range top-k query is a powerful tool for analysis in spatial databases and data warehouse environments. In this paper, we propose an algorithm to answer the query by selectively traversing an aggregate R-tree having MAX as the aggregate values. The algorithm can execute the query by accessing only a small part of the leaf nodes within a query region. Therefore, it shows good query performance regardless of the size of the query region. We suggest an efficient pruning technique for the priority queue, which reduces the cost of handling the priority queue, and also propose an efficient technique for leaf node organization to reduce the number of node accesses to execute the range top-k queries.
Jingyu XU Xianlong HONG Tong JING
Timing optimization is an important goal of global routing in deep submicron era. To guarantee the timing performance of the circuit, merely adopting topology optimization becomes inadequate. In this paper, we present an efficient timing-driven global routing algorithm with buffer insertion. Our approach is capable of applying topological-based timing optimization and buffer insertion simultaneously with routablity considerations. Compared with previous works, we efficiently solve the timing issues under a limited buffer usage. The experimental results have demonstrated significant delay improvement within short runtime with very small number of buffers inserted.