Jun ANZAI Natsume MATSUZAKI Tsutomu MATSUMOTO
This paper proposes a group key distribution scheme with a user exclusion. The user exclusion is how to distribute an encryption key over a broadcast channel shared by n users so that all but d excluded users can get the group key. In the broadcast channel such as Pay-TV, Internet multicast and a mobile telecommunication for a group, a manager should exclude a dishonest user or an unauthorized terminal as soon as possible to protect the secrecy of the group communication. However, it takes a long time for the user exclusion on a large group, if the distributor distributes the group key to each user except the excluded one. We propose a scheme in which the amount of transmission and the key storage of each user do not depend on the number of users of the group. Moreover, our scheme does not require a fixed and privileged distributor.
This paper deals with deadlock and fairness issues that may arise when network users request resources for guaranteed service with the resource reservation protocol (RSVP). A deadlock occurs when a request can only be satisfied if the resources reserved for another request are released, but the reserved resources are never released. The fairness issue occurs when some reservation requests may be satisfied but only after a very long wait. Our approach to these issues is based on our belief that a network should provide stable throughput and fairness whatever the behavior of the user. Our methods are unique in two respects. First, during the session setup phase, a node directly connected to the requesting users terminates the users' behavior and makes reservations fairly and efficiently in place of the users. Second, our three admission control methods allocate resources for each reservation request by considering not only the current residual bandwidth but also the properties of the requesting session; e.g., its weight (the number of resources it requires) or its age (how long it has been waiting for session setup). Our methods do not maximize the throughput since they always keep a certain amount of resources unreserved for fairness. From simulation results, however, they do provide quite fair behavior, and their throughput is stable regardless of the network size and the session holding time.
Ssang-Soo LEE Chang-Hyung LEE Seung-Woo SEO
In this paper, we investigate the blocking characteristics of all-optical WDM (Wavelength-Division Multiplexing) networks under distributed wavelength assignment policies. For assigning wavelengths in a distributed manner, we consider two algorithms: random and locally-most-used algorithm. For a random wavelength assignment policy, we develop new blocking models of unidirectional/bidirectional ring networks based on the M/M/c/c queueing models under uniform/nonuniform traffic conditions. These models are shown to be more accurate than the previous blocking models since our approach considers the large traffic correlation among links in ring networks. We also analyze the blocking performance of the locally-most-used algorithm by comparing with that of the globally-most-used algorithm in fixed routing networks. We show that our analysis models match well with the simulation results in ring and mesh networks. Through the comparison with the previous centralized/distributed algorithms, it is demonstrated that the distributed locally-most-used algorithm is computationally efficient with good blocking performance.
Taiichi SAITO Takeshi KOSHIBA Akihiro YAMAMURA
This paper examines similarities between the Decision Diffie-Hellman (DDH) assumption and the Quadratic Residuosity (QR) assumption. In addition, we show that many cryptographic protocols based on the QR assumption can be reconstructed using the DDH assumption.
In most access control systems, authorization is specified using binary decisions, "yes" or "no," to the access requests resulting in access being permitted or denied respectively. We argue that emerging Internet applications require that this binary decision be extended to "allow access provided some actions are taken. " We propose the notion of provisional actions that specifies the necessary actions to be performed in addition to the binary decision and introduce an access control model for it. We also provide an administrative model for policy management purpose.
In this paper, we consider the complexity of recognizing ordered tree-shellable Boolean functions when Boolean functions are given as OBDDs. An ordered tree-shellable function is a positive Boolean function such that the number of prime implicants equals the number of paths from the root node to a 1-node in its ordered binary decision tree representation. We show that given an OBDD, it is possible to check within polynomial time if the function is ordered tree-shellable with respect to the variable ordering of the OBDD.
Satoshi UNO Hideki TODE Koso MURAKAMI
B-ISDN is expected to be applied in the near future to video delivery systems for the broadcast of news and television programs. The demand for such services is increasing, and in particular, on-demand services are becoming more desirable. On-demand services allow viewers to request their favorite programs at the time that is convenient, hence catering for the wide range of modern lifestyles. As for on-demand services, there already exist Video on Demand (VoD) systems such as the original VoD or Near VoD. However, such systems have not yet been widely implemented because of the inefficient cost of communication resources, and storage. The authors' research is aimed at producing an efficient VoD system based on a high speed network. We are focused in particular on the forms of data transmission, and in this paper, we propose a new VoD system called Burst VoD. Burst VoD aggressively utilizes the multicasting technique, and involves dividing the program resource data into block files and transmitting them to viewer terminals as burst traffic over a high speed network. Simulation results comparing Burst VoD with conventional VoD show that Burst VoD achieves lower request blocking rates, efficient utilization of networks with multicasting, and almost on-demand response time to requests.
The use of the column-rank of the system sensitivity matrix as a testability measure for parametric faults in linear analog circuits was pioneered by Sen and Saeks in 1970s, and later re-introduced by several others. Its practical use has been limited by how it can be calculated. Numerical algorithms suffer from inevitable round-off errors, while traditional symbolic techniques can only handle very small circuits. In this paper, an efficient method is introduced for the analysis of Sen and Saeks' analog testability. The method employs determinant decision diagram based symbolic circuit analysis. Experimental results have demonstrated the new method is capable of handling much larger analog circuits.
A Generalized Hypercube Network (GHNet) with shared channels which requires only one fixed-wavelength transmitter and r(m-1) fixed-wavelength receivers per node is proposed. The proposed network topology reduces not only the number of transmitters per node but also the number of WDM channels required to service the same number of nodes compared with the GHNet with dedicated channels by sharing the available WDM channels, while it maintains the same channel efficiency as the GHNet with dedicated channels. The proposed network topology may be preferred in a situation where the number of available WDM channels and the cost of the transmitter may cause a major restriction on the lightwave network construction. For performance analysis, the network capacity and the mean queueing delay for the proposed network topology are obtained. Also, the performance measures of the proposed GHNet with shared channels are compared with those of the ShuffleNet with shared channels.
Aria ABUBAKAR Peter M. van den BERG Bert Jan KOOIJ
A method for determination of the location, shape, and material properties of a 3D object from measurements of the scattered field, when the object is successively illuminated by a number of incident fields is presented. This work extends the method previously developed for reconstructions of 2D permittivity and conductivity from electromagnetic measurements to the more complicated full-vector 3D electromagnetic inversion. Furthermore, a frequency hopping strategy to improve the resolution of the unknown objects when the frequency is raised, is underlined. Results of numerical experiments are presented to illustrate both strengths and weaknesses of the method.
Jong-Il PARK Kyeong Ho YANG Yuichi IWADATE
This Letter proposes a new three dimensional (3D) visual communication approach based on the image-based rendering. We first compactly represent a reference view set by exploiting its geometric correlation and then efficiently compress the representation with appropriate coding schemes. Experimental results demonstrate that our proposed method significantly reduces the required bitrate.
Tetsushi KATAYAMA Hiroyuki OCHI Takao TSUDA
Binary Decision Diagrams (BDDs) are graph representation of Boolean functions. In particular, Ordered BDDs (OBDDs) are useful in many situations, because they provide canonical representation and they are manipulated efficiently. BDD packages which automatically generate OBDDs have been developed, and they are now widely used in logic design area, including formal verification and logic synthesis. Synthesis of pass-transistor circuits is one of successful applications of such BDD packages. Pass-transistor circuits are generated from BDDs by mapping each node to a selector which consists of two or four pass transistors. If circuits are generated from smaller BDDs, generated circuits have smaller number of transistors and hence save chip area and power consumption. In this paper, more generic BDDs which have no restrictions in variable ordering and variable appearance count on its paths are called Generic BDDs (GBDDs), and an algorithm for generating GBDDs is proposed for the purpose of synthesis of pass-transistor circuits. The proposed algorithm consists of two steps. At the first step, parse trees (PTs) for given Boolean formulas are generated, where a PT is a directed tree representation of Boolean formula(s) and it consists of literal nodes and operation nodes. In this step, our algorithm attempts to reduce the number of literal nodes of PTs. At the second step, a GBDD is generated for the PTs using Concatenation Method, where Concatenation Method generates a GBDD by connecting GBDDs vertically. In this step, our algorithm attempts to share isomorphic subgraphs. In experiments on ISCAS'89 and MCNC benchmark circuits, our program successfully generated 32 GBDDs out of 680 single-output functions and 4 GBDDs out of 49 multi-output functions whose sizes are smaller than OBDDs. GBDD size is reduced by 23.1% in the best case compared with OBDD.
Jae-Soo CHO Do-Jong KIM Dong-Jo PARK
A real-time adaptive segmentation method based on new distance features is proposed for the binary centroid tracker. These novel features are distances between the predicted center pixel of a target object by a tracking filter and each pixel in extraction of a moving target. The proposed method restricts clutters with target-like intensity from entering a tracking window and has low computational complexity for real-time applications compared with other complex feature-based methods. Comparative experiments show that the proposed method is superior to other segmentation methods based on the intensity feature only in target detection and tracking.
Hafiz Md. HASAN BABU Tsutomu SASAO
In this paper, we propose a method to minimize multiple-valued decision diagrams (MDDs) for multiple-output functions. We consider the following: (1) a heuristic for encoding the 2-valued inputs; and (2) a heuristic for ordering the multiple-valued input variables based on sampling, where each sample is a group of outputs. We first generate a 4-valued input 2-valued multiple-output function from the given 2-valued input 2-valued functions. Then, we construct an MDD for each sample and find a good variable ordering. Finally, we generate a variable ordering from the orderings of MDDs representing the samples, and minimize the entire MDDs. Experimental results show that the proposed method is much faster, and for many benchmark functions, it produces MDDs with fewer nodes than sifting. Especially, the proposed method generates much smaller MDDs in a short time for benchmark functions when several 2-valued input variables are grouped to form multiple-valued variables.
Hiroshi SAWADA Shigeru YAMASHITA Akira NAGOYA
This paper presents a new method that efficiently generates all of the kernels of a sum-of-products expression. Its main feature is the memorization of the kernel generation process by using a graph structure and implicit cube set representations. We also show its applications for common logic extraction. Our extraction method produces smaller circuits through several extensions than the extraction method based on two-cube divisors known as best ever.
Sumitaka SAKAUCHI Yoichi HANEDA Shoji MAKINO Masashi TANAKA Yutaka KANEDA
We investigated the dependence of the desired echo return loss on frequency for various hands-free telecommunication conditions by subjective assessment. The desired echo return loss as a function of frequency (DERLf) is an important factor in the design and performance evaluation of a subband echo canceller, and it is a measure of what is considered an acceptable echo caused by electrical loss in the transmission line. The DERLf during single-talk was obtained as attenuated band-limited echo levels that subjects did not find objectionable when listening to the near-end speech and its band-limited echo under various hands-free telecommunication conditions. When we investigated the DERLf during double-talk, subjects also heard the speech in the far-end room from a loudspeaker. The echo was limited to a 250-Hz bandwidth assuming the use of a subband echo canceller. The test results showed that: (1) when the transmission delay was short (30 ms), the echo component around 2 to 3 kHz was the most objectionable to listeners; (2) as the transmission delay rose to 300 ms, the echo component around 1 kHz became the most objectionable; (3) when the room reverberation time was relatively long (about 500 ms), the echo component around 1 kHz was the most objectionable, even if the transmission delay was short; and (4) the DERLf during double-talk was about 5 to 10 dB lower than that during single-talk. Use of these DERLf values will enable the design of more efficient subband echo cancellers.
Jerome J. AKERSON Yingching Eric YANG Yoshihisa HARA Bae-Ian WU Jin A. KONG
In Synthetic Aperture Radar Interferometry (InSAR), phase unwrapping holds the key to accurate inversion of digital elevation data. Two new techniques are introduced in this paper that can perform automatic phase unwrapping. The first one is an "optimal" branch-cut algorithm and the second one a hybrid branch-cut/least-square technique, in which pole locations form the weighting basis for the weighted least-square approach. Application of both techniques to ERS-1 data indicates that the height inversion errors are comparable and offer over fifty percent reduction in root mean square (rms) height error compared to the straight least squares method and over thirty-five percent reduction in rms height error compared to the weighted least squares method based on coherence data weighting schemes. The hybrid technique is especially appealing due to its computational efficiency and robustness when compared to traditional branch-cut algorithms.
Miki YAMAMOTO Takashi HASHIMOTO Hiromasa IKEDA
In reliable multicast communications, retransmission control plays an important role from the viewpoint of scalability. Previous works show that the implosion of control packets, e.g. ACKs or NAKs, degrades the total performance of reliable multicast communications. Local recovery which enables receivers receiving a packet successfully to initiate recovering a lost packet may have the possibility to solve this scalability problem. This paper presents the performance evaluation of local recovery caused by grouping receiving nodes in reliable multicast communication. There seems to be many features dominating the performance of local recovery, the number of nodes in a group, the shared loss occurring simultaneously at multiple receivers and so on. When the number of receivers in a group increases, the geographical expansion of a group will degrade the delay performance of the receivers. In a configuration where most nodes in a local-recovery group suffer from shared loss, the failure of local recovery degrades the total performance. Our simulation results under a hierarchical network topology like the real Internet show that a local-recovery group configuration with two-adjacent MANs grouping performs well.
The maximum likelihood estimate of a mixture model is usually found by using the EM algorithm. However, the EM algorithm suffers from a local optima problem and therefore we cannot obtain the potential performance of mixture models in practice. In the case of mixture models, local maxima often have too many components of a mixture model in one part of the space and too few in another, widely separated part of the space. To escape from such configurations we proposed a new variant of the EM algorithm in which simultaneous split and merge operations are repeatedly performed by using a new criterion for efficiently selecting the split and merge candidates. We apply the proposed algorithm to the training of Gaussian mixtures and the dimensionality reduction based on a mixture of factor analyzers using synthetic and real data and show that the proposed algorithm can markedly improve the ML estimates.
Kensaku FUJII Yoshinori TANAKA
The signed regressor algorithm, a variation of the least mean square (LMS) algorithm, is characterized by the estimation way of using the clipped reference signals, namely, its sign (). This clipping, equivalent to quantizing the reference signal to 1, only increases the estimation error by about 2 dB. This paper proposes to increase the number of the quantization steps to three, namely, 1 and 0, and shows that the 'tri-quantized-x' normalized least mean square (NLMS) algorithm with three quantization steps improves the convergence property.