Youki KADOBAYASHI Satoshi ABE Yasuhiro OHARA Masaki MINAMI
This paper presents an architecture for content internetworking, which we call CRN (Content Routing Network) architecture. The CRN architecture is different from other content internetworking architectures in many respects: the peering of authentication, authorization and accounting systems, hierarchical and policy-driven request routing, and the web-based system to interconnect distinct CDNs. Both requirements and functional architecture of CRN are presented, followed by the description of its prototypical implementation. CRN is designed to satisfy both content provider's service requirements and service provider's economic/operational requirements. A prototypical implementation has been deployed successfully under one of the biggest live-streaming experiments.
Hiroshi KUBO Masayuki MATSUSHITA Ikuo AWAI
The radiation patterns are synthesized by properly disposing surface variations on dielectric rod waveguides. The genetic algorithm (GA) is applied for searching the optimum disposition of variation sections. A very fast calculation method used in the optimization is presented. The guided waves are related in the form of a 2-port circuit and the radiation field is expressed by superposition of the waves from variation sections. Various conical beams can be synthesized. Short variation sections and combination of several variation sections with different height are used to improve the synthesis performance. The ripple of the mainlobe and the sidelobe levels become small. Spherical sector patterns with a steep fall are synthesized and the agreement with the experimental values is confirmed.
Hiroshi TSUNODA Kohei OHTA Nei KATO Yoshiaki NEMOTO
Mobility management is a core issue in IP/LEO satellite network related research. The LEO system consists of wide network of moving satellites providing connectivity to any place on the earth. It implies that the system must support numerous wireless connections under high-mobility conditions. Existing mobility management protocols like Mobile IP suppose that two types of identities, indicating a unique name and position in the network, are dynamically bound in each handover. However, in the IP/LEO system, handovers are mainly caused by fast moving satellites, not moving nodes. As a result, quite a few binding update requests are generated during a short period by the moving satellites; this makes mobility management difficult. In this paper, we propose a new mobility management method that separates binding updates from handovers by using geographical location of the nodes. We evaluate the proposed method and show its effectiveness.
Koichi ICHIGE Masashi SHINAGAWA Hiroyuki ARAI
This paper studies on a fast approach for the eigenproblems of correlation matrices used in direction-of-arrival (DOA) estimation algorithms, especially for the case that the number of arriving waves is a few. The eigenvalues and the corresponding eigenvectors can be obtained in a very short time by the algebraic solvent of up to quartic polynomials. We also confirm that the present approach does not make the accuracy worse when it is implemented by finite word-length processors like digital signal processor (DSP) or field programmable gate array (FPGA).
Takao OGURA Junji SUZUKI Akira CHUGO Masafumi KATOH Tomonori AOYAMA
As use of the Internet continues to spread rapidly, Traffic Engineering (TE) is needed to optimize IP network resource utilization. In particular, load balancing with TE can prevent traffic concentration on a single path between ingress and egress routers. To apply TE, we have constructed an MPLS (Multi-Protocol Label Switching) network with TE capability in the JGN (Japan Gigabit Network), and evaluated dynamic load balancing behavior in it from the viewpoint of control stability. We confirmed that with this method, setting appropriate control parameter values enables traffic to be equally distributed over two or more routes in an actual large-scale network. In addition, we verified the method's effectiveness by using a digital cinema application as input traffic.
Haruo KOBAYASHI Hiroshi YAGI Takanori KOMURO Hiroshi SAKAYORI
This paper describes two digital correction algorithms for ADC nonlinearity, targeted for mixed-signal LSI tester applications: an interpolation algorithm and a stochastic algorithm. Numerical simulations show that our algorithms compensate for ADC nonlinearity as well as missing codes and nonmonotonicity characteristics, and improve ADC SNDR and SFDR.
Ikjun YEOM A. L. Narasimha REDDY
Class-based delay differentiation model has been recently proposed as a part of relative differentiated services frameworks, and it is shown that the model can provide delay differentiation without admission control and end-to-end resource reservation. In this paper, however, we observe that there can be inconsistent delay differentiation caused by different size of packets. We propose packet size-based delay differentiation model and show that packet size-based queueing is effective to achieve equal delay within a class and provide consistent delay differentiation between classes through simulations. Simulation results also show that the proposed model improves jitter characteristics of CBR flows.
Katsuya MINAMI Hideki TODE Koso MURAKAMI
As multimedia and high-speed traffic become more popular on the Internet, the various traffic requiring different qualities of service (QoS) must co-exist. In addition, classified services based on Diff-Serv (Differentiated Service), MPLS (Multi-Protocol Label Switching), etc., have come into wide use. Today's Internet environment requires routers to perform control mechanisms in order to guarantee various QoSs. In this paper, we propose a smart buffer management scheme for the Internet router that uses hierarchical priority control with port class and flow level. Furthermore, since the proposed scheme must operate at very high speed, we first propose several design policy for high speed operation and the hardware implementation is performed in VHDL code. Implementation results show that the proposed scheme can scale with high-speed link, achieving the maximum rate of 4.0 Gbps by using the 3.5 µm CMOS technology.
An adaptive congestion control scheme that can be applied to various random access protocols in mobile communication systems is proposed. Its main features are scalability for handling increasing numbers of mobile terminals and adaptability for coping with drastic changes in traffic load. These are achieved by controlling the traffic load adaptively to maintain maximum throughput even under overload conditions. Procedure for measuring and estimating offered traffic and a method of setting control thresholds that maximize the average throughput are analytically derived, and the algorithm for adaptively controlling the permission rate is described. This scheme was applied to both the slotted ALOHA and ICMA/CD protocols. For each protocol, three control parameters--the unsuccessful rate, optimal traffic, and control thresholds--were analytically derived. Then stationary throughput characteristics were numerically evaluated. We found that the scheme could achieve high throughput by regulating transmission adaptively depending on the offered traffic. The preferred range of the permission base rate that enables adaptive control and limits the amount of processing at terminals was also clarified. Since one of the main advantages of our scheme is its adaptability to drastic variations in traffic load, we simulated its transient characteristics with three types of time-variant input models. The results indicate that this control scheme achieved nearly theoretically optimal throughput even during an overload for each input model.
Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. This paper surveys how algorithm engineering can contribute to digital halftoning or what combinatorial problems are related to digital halftoning. A common criterion on optimal digital halftoning leads to a negative result that obtaining an optimal halftoned image is NP-complete. So, there are two choices: approximation algorithm and polynomial-time algorithm with relaxed condition. Main algorithmic notions related are geometric discrepancy, matrix (or array) rounding problems, and network-flow algorithms.
Toshinori TAKAI Hiroyuki SEKI Youhei FUJINAKA Yuichi KAJI
A term rewriting system which effectively preserves recognizability (EPR-TRS) has good mathematical properties. In this paper, a new subclass of TRSs, layered transducing TRSs (LT-TRSs) is defined and its recognizability preserving property is discussed. The class of LT-TRSs contains some EPR-TRSs, e.g., {f(x)f(g(x))} which do not belong to any of the known decidable subclasses of EPR-TRSs. Bottom-up linear tree transducer, which is a well-known computation model in the tree language theory, is a special case of LT-TRS. We present a sufficient condition for an LT-TRS to be an EPR-TRS. Also reachability and joinability are shown to be decidable for LT-TRSs.
In estimating the channels for OFDM, ESAE has better performance than PSAM. But ESAE has the "run-away" phenomenon if the channel estimation errors accumulate. In the proposed Assisted Pilot for Improvement and stability of Mobile communication system (APIM) method, pilots used in PSAM, additional pilots and some pre-estimated channels are applied to estimate the channel. The experimental results show that the proposed method, APIM, significantly outperforms conventional methods in terms of MSE and BER under Rayleigh fading environment and has stable characteristics even in the high-speed mobile communication system.
Hiroki SATO Akira HYOGO Keitaro SEKINE
The square-law characteristics of MOSFET in the saturation region have a parameter of threshold voltage VT. However, it introduces some complexities to the circuit design since it depends on kinds of MOS technology and cannot be controlled easily. In this paper, we show an equivalent MOSFET cell which has VT-programming capability and some application instances based on it. The simulation is carried out using CMOS 0.8 µm n-well technology and the results have shown the feasibility of the proposed structure.
Yukihiro TAHARA Hideyuki OH-HASHI Moriyasu MIYAZAKI
This paper describes a three-port power divider with compensation networks for non-ideal isolation resistor. The compensation networks consist of two pairs of transmission lines and cancel out the parasitic reactance of the non-ideal isolation resistor. The design equations to provide perfect return loss and isolation at a center frequency are presented. The availability of the proposed power divider has been verified by the comparison between calculated and experimental results in the Ku-band.
Yoshinori TAKEI Toshinori YOSHIKAWA Xi ZHANG
As pseudorandom number generators for Monte Carlo simulations, inversive linear congruential generators (ICG) have some advantages compared with traditional linear congruential generators. It has been shown that a sequence generated by an ICG has a low discrepancy even if the length of the sequence is far shorter than its period. In this paper, we formulate fractional linear congruential generators (FCG), a generalized concept of the inversive linear congruential generators. It is shown that the sequence generated by an FCG is a geometrical shift of a sequence from an ICG and satisfies the same upper bounds of discrepancy. As an application of the general formulation, we show that under certain condition, "Leap-Frog technique," a way of splitting a random number sequence to parallel sequences, can be applied to the ICG or FCG with no extra cost on discrepancy.
In this paper, we consider the problem of multicasting a message in k-ary n-cubes under the store-and-forward model. The objective of the problem is to minimize the size of the resultant multicast tree by keeping the distance to each destination over the tree the same as the distance in the original graph. In the following, we first propose an algorithm that grows a multicast tree in a greedy manner, in the sense that for each intermediate vertex of the tree, the outgoing edges of the vertex are selected in a non-increasing order of the number of destinations that can use the edge in a shortest path to the destination. We then evaluate the goodness of the algorithm in terms of the worst case ratio of the size of the generated tree to the size of an optimal tree. It is proved that for any k 5 and n 6, the performnance ratio of the greedy algorithm is c kn - o(n) for some constant 1/12 c 1/2.
Masataka TAKAMURA Yoshihide IGARASHI
We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.
In this paper, parallelization methods for quantum circuits are studied, where parallelization of quantum circuits means to reconstruct a given quantum circuit to one which realizes the same quantum computation with a smaller depth, and it is based on using additional bits, called ancillae, each of which is initialized to be in a certain state. We propose parallelization methods in terms of the number of available ancillae, for three types of quantum circuits. The proposed parallelization methods are more general than previous one in the sense that the methods are applicable when the number of available ancillae is fixed arbitrarily. As consequences, for the three types of n-bit quantum circuits, we show new upper bounds of the number of ancillae for parallelizing to logarithmic depth, which are 1/log n of previous upper bounds.
Muneo KUSHIMA Koichi TANNO Okihiko ISHIZUKA
In this paper, a voltage-controlled linear variable resistor (VCLVR) using a floating-gate MOSFET (FG-MOSFET) is proposed. First, the grounded VCLVR realization is discussed. The proposed circuit consists of only an ordinary MOSFET and an FG-MOSFET. The advantages of the proposed VCLVR are low-power and wide-input range and also the power consumption of the proposed VCLVR is the same as an ordinary passive resistor. The performance of the proposed circuits are confirmed by HSPICE simulations with a standard 0.6 µm CMOS process parameters. Simulations of the proposed VCLVR demonstrate a resistance value of 40 kΩ to 338 kΩ and an input range of 4.34 V within THD of less than 1.1%. Next, we proposed a new floating node linear variable resistor using the proposed VCLVR. The performance of the circuit is also evaluated through HSPICE.
Kenta HASHIMOTO Toshinori YAMADA Shuichi UENO
We consider the routing for a multicast in a WDM all-optical network. We prove a min-max theorem on the number of wavelengths necessary for routing a multicast. Based on the min-max theorem, we propose an efficient on-line algorithm for routing a multicast.