TCP congestion control is receiving increased attention in recent years due to their usefulness for network stability, robustness use of network buffer and bandwidth resources on an end-to-end per-connection basis. The RED scheme was designed for a network where a single dropped packet is sufficient to signal the presence of congestion to the TCP protocol. This paper applies matrix-analytic approach to analyze both the long-term and the short-term drop behaviors of a queue with RED scheme and uses this model to quantify the benefits brought about by RED. The result shows that the drop probability between RED and Drop-Tail is very close under heavy load conditions. This indicates that RED not only can resolve the synchronization problem but also has the same loss performance with Drop-Tail scheme under the heavy load circumstances. Our findings also show that the rate oscillation behavior of RED is better than Drop-Tail when TCP applies the additive-increase and multiplication-decrease mechanism. As a consequence, it can help reduce the required buffer capacity in the RED router.
Junho JEONG Jitae SHIN Doug Young SUH
In the past, enhancement techniques for the end-to-end quality of a networked application were studied by looking at each individual layer. Examples of such techniques include the error resilience/concealment methods in the application layer, the FEC/ARQ in the transport layer, and the Quality of Service (QoS) techniques in the network layers. However, an integrated approach that would look across all related layers had yet to be investigated. This paper proposes an approach that combines priority-aware video packetization, adaptively used layered FEC, and QoS controlled networks such as IntServ and DiffServ in order to provide an efficient end-to-end quality in layered streaming video. The combination is more efficient in terms of a simple network price mechanism, that is, in getting the best end-to-end quality under a given total cost constraint. Our proposed approach in DiffServ with video packet (VP) data-splitting and layered FEC guarantees minimal service quality in a scalable and cost effective manner without introducing resource reservation. For video, we also propose performance metrics such as corrupted/frozen frame ratio (CFR, FFR). These provide objective metrics like PSNR as well as a measurement for subjective perceptions. Our approach, which combines related layers such as video coding, transport, and network, has yielded results that have proven to be more cost-effective and practical than the supporting network QoS.
Qing-Xin CHU Xiao-Juan HU Kam-Tai CHAN
In the FDTD simulation of microwave circuits, a device in very small size compared with the wavelength is often handled as a lumped element, but it may still occupy more than one cell instead of a wire structure without volume routinely employed in classical extended FDTD algorithms. In this paper, two modified extended FDTD algorithms incorporating a lumped element occupying more than one cell are developed directly from the integral form of Maxwell's equations based on the assumption whether displacement current exists inside the region where a device is present. If the displacement current exists, the modified extended FDTD algorithm can be represented as a Norton equivalent current-source circuit, or otherwise as a Thevenin equivalent voltage-source circuit. These algorithms are applied in the microwave line loaded by a lumped resistor and an active antenna to illustrated the efficiency and difference of the two algorithms.
Kouji WADA Yoshiyuki AIHARA Osamu HASHIMOTO Hiroshi HARADA
Basic characteristics of a short-ended half-wavelength resonator made of a coplanar waveguide (CPW) and their applications to bandpass filters (BPFs) are discussed. The first part of this paper gives the essence for improving out-of-band characteristics of the BPF by describing the basic characteristics of a tap-coupled resonator. Secondly, a new BPF with attenuation poles using the short-ended half-wavelength CPW resonators is proposed and realized. It is confirmed that our methodology is useful for improving out-of-band characteristics of the BPF using the short-ended half-wavelength CPW resonators without complicated filter design.
Min-Shiang HWANG Cheng-Chi LEE Yan-Chi LAI
Recently, Stadler et al. proposed the concept of fair blind signatures to prevent the misuse of blind signature schemes from criminals. In this article, we show the proposed scheme could not meet the untraceability property of blind signature's requirements. We point out that the proposed scheme cannot provide true blind signatures.
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.
This paper presents a miniaturized reverse-phase hybrid ring by the use of shunt capacitors, and successfully designs a very miniature hybrid ring of a 0.28-wavelength circumference with a wide bandwidth comparable to the regular reverse-phase hybrid ring based on the equivalent admittance approach. Moreover, a method of broadening the bandwidth with adding a matching network consisting of a very short transmission line and two shunt capacitors at each port is also described. The validity of the proposed design is demonstrated by electromagnetic simulator (Sonnet em) for a uniplanar hybrid ring.
Xiaotong HU Makoto FUJIMURA Yoko MAEMURA Hideo KURODA
In fractal image coding, for each range block, the best matching domain block is identified, and information from the best matching domains and range blocks are transmitted to the decoder for image reconstruction. In this paper, the similarity between range blocks and domain blocks is evaluated according to their centers of gravity. The number of searched domain blocks are reduced by limiting the candidates for the best matching domain blocks to those domain blocks whose similarity to the range block are high. Using simulation experiments, the number of candidates for the best matching domain blocks were reduced to about 10-23% of the current method. Thus, our proposed method had significantly reduced the number of searched domain blocks below the current method and at the same time it turns out that degradation of the reconstructed image was seldom observed.
Katsutoshi SAEKI Yoshifumi SEKINE
In this paper, we propose the CMOS implementation of neuron models for an artificial auditory neural network. We show that when voltage is added directly to the control terminal of the basic circuit of the hardware neuron model, a change in the output firing is observed. Next, based on this circuit, a circuit that changes with time is added to the control terminal of the basic circuit of the hardware neuron model. As a result, a neuron model is constructed with ON firing, adaptation firing, and repetitive firing using CMOS. Furthermore, an improved circuit of a neuron model with OFF firing using CMOS which has been improved from the previous model is also constructed.
In this paper, we investigate the performance of Mobile IP regional registration and compare it with that of Mobile IP. The performance measures used are registration delay and the CPU processing overheads loaded on the agents to handle mobility of mobile nodes. Through the investigation, the effectiveness of adopting Mobile IP regional registration in the wide-area wireless network in terms of reducing the CPU processing overheads on the home agent and lowering the signaling delay is observed. We also compare the scalability of Mobile IP regional registration schemes when two and three levels of foreign agent hierarchy are considered. Based on the comparison, we propose a network design strategy for achieving optimized performance and cost.
In this paper, we describe the development and the analysis of the Label Distribution Protocol (LDP) for Multiprotocol Label Switching System. We review the implementation issues that are required to construct the LDP for a gigabit switched router and propose a detailed design of the LDP. We present the detailed design using the Deviation Tree of the protocol state machine and a formal specification of the state machine using the process algebra. These specifications are based on the IETF standard. By analyzing the protocol behaviors of the Deviation Trees and the formal specification, we prove the interoperability, completeness, liveness, reachability, and the safety of the implemented LDP. We expect that the reliability would be improved using these analyses. With these proofs we expect the implemented LDP will be interoperable with other commercialized products. As a result we validate the protocol behaviors of the implemented LDP.
Masashi KAWAGUCHI Takashi JIMBO Masayoshi UMENO
We propose herein a motion detection artificial vision model which uses analog electronic circuits. The proposed model is comprised of four layers. The first layer is a differentiation circuit of the large CR coefficient, and the second layer is a differentiation circuit of the small CR coefficient. Thus, the speed of the movement object is detected. The third layer is a difference circuit for detecting the movement direction, and the fourth layer is a multiple circuit for detecting pure motion output. When the object moves from left to right the model outputs a positive signal, and when the object moves from right to left the model outputs a negative signal. We first designed a one-dimensional model, which we later enhanced to obtain a two-dimensional model. The model was shown to be capable of detecting a movement object in the image. Using analog electronic circuits, the number of connections decrease and real-time processing becomes feasible. In addition, the proposed model offers excellent fault tolerance. Moreover, the proposed model can be used to detect two or more objects, which is advantageous for detection in an environment in which several objects are moving in multiple directions simultaneously. Thus, the proposed model allows practical, cheap movement sensors to be realized for applications such as the measurement of road traffic volume or counting the number of pedestrians in an area. From a technological viewpoint, the proposed model facilitates clarification of the mechanism of the biomedical vision system, which should enable design and simulation by an analog electric circuit for detecting the movement and speed of objects.
Javad HADDADNIA Karim FAEZ Majid AHMADI Payman MOALLEM
This paper presents an efficient Hybrid Learning Algorithm (HLA) for Radial Basis Function Neural Network (RBFNN). The HLA combines the gradient method and the linear least squared method for adjusting the RBF parameters and connection weights. The number of hidden neurons and their characteristics are determined using an unsupervised clustering procedure, and are used as input parameters to the learning algorithm. We demonstrate that the HLA, while providing faster convergence in training phase, is also less sensitive to training and testing patterns. The proposed HLA in conjunction with RBFNN is used as a classifier in a face recognition system to show the usefulness of the learning algorithm. The inputs to the RBFNN are the feature vectors obtained by combining shape information and Pseudo Zernike Moment (PZM). Simulation results on the Olivetti Research Laboratory (ORL) database and comparison with other algorithms indicate that the HLA yields excellent recognition rate with less hidden neurons in human face recognition.
Hanmin JUNG Gary Geunbae LEE Won Seug CHOI KyungKoo MIN Jungyun SEO
This paper describes a highly-portable multilingual question answering system on multiple relational databases. We apply techniques which were verified on open-domain text-based question answering, such as semantic category and pattern-based grammars, into natural language interfaces to relational databases. Lexico-semantic pattern (LSP) and multi-level grammars achieve portability of languages, domains, and DB management systems. The LSP-based linguistic processing does not require deep analysis that sacrifices robustness and flexibility, but can handle delicate natural language questions. To maximize portability, we drive three dependency factors into the following two parts: language-dependent part into front linguistic analysis, and domain-dependent and database-dependent parts into backend SQL query generation. We also support session-based dialog by preserving SQL queries created from previous user's question, and then re-generating new SQL query for the successive questions. Experiments with 779 queries generate only constraint-missing errors, which can be easily corrected by adding new terms, of 2.25% for English and 5.67% for Korean.
Hiroshi NAGAMOCHI Shuji NAKAMURA Toshimasa ISHII
It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with O(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in O(mn+n2log n) time and O(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.
Tomoya FUJINO Shuji ISOBE Xiao ZHOU Takao NISHIZEKI
Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). It is known that any series-parallel simple graph G has an L-edge-coloring if either (i) |L(e)| max{4,d(v),d(w)} for each edge e=vw or (ii) the maximum degree of G is at most three and |L(e)| 3 for each edge e, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. In this paper we give a linear-time algorithm for finding such an L-edge-coloring of a series-parallel graph G.
Takehiro ITO Takao NISHIZEKI Xiao ZHOU
Let each vertex v of a graph G have a positive integer weight ω(v). Then a multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.
Masatoshi MORITA Katsushi INOUE Akira ITO Yue WANG
This paper investigates properties of space-bounded "two-dimensional Turing machines (2-tm's)," whose input tapes are restricted to square ones, with bounded input head reversals in vertical direction. We first investigate a relationship between determinism and nondeterminism for space-bounded and input head reversal-bounded 2-tm's. We then investigate how the number of input head reversals affects the accepting power of sublinearly space-bounded 2-tm's. Finally, we investigate necessary and sufficient spaces for three-way 2-tm's to simulate four-way two-dimensional finite automata with constant input head reversals.
Eiju HIROWATARI Kouichi HIRATA Tetsuhiro MIYAHARA Setsuo ARIKAWA
This paper investigates the interaction of mind changes and anomalies for inductive inference of recursive real-valued functions. We show that the criteria for inductive inference of recursive real-valued functions by bounding the number of mind changes and anomalies preserve the same hierarchy as that of recursive functions, if the length of each anomaly as an interval is bounded. However, we also show that, without bounding it, the hierarchy of some criteria collapses. More precisely, while the class of recursive real-valued functions inferable in the limit allowing no more than one anomaly is properly contained in the class allowing just two anomalies, the latter class coincides with the class allowing arbitrary and bounded number of anomalies.
This paper defines the distributed arrangement selection problem in a line network in a distributed context and describes the design of a strictly-time-optimal algorithm which solves the problem with a limited local memory space. The problem is regarded as a combined distributed sorting and k-selection problem, namely a problem of sorting elements that are not larger than the kth minimum element in predetermined processes. The algorithm also provides a solution to a resource allocation problem in a line network in a strictly-optimal time.