In this paper we addresses the problem of finding feasible solutions for the Group Multicast Routing Problem (GMRP). This problem is a generalization of the multicast routing problem whereby every member of the group is allowed to multicast messages to other members from the same group. The routing problem involves the construction of a set of low cost multicast trees with bandwidth requirements for all the group members in the network. We first prove that the problem of finding feasible solutions to GMRP is NP-complete. Following that we propose a new heuristic algorithm for constructing feasible solutions for GMRP. Simulation results show that our proposed algorithm is able to achieve good performance in terms of its ability of finding feasible solutions whenever one exist.
Naoyuki SHIMADA Katsuhiro YUTANI Masahiro UEMUKAI Toshiaki SUHARA Anders LARSSON
A tunable external-cavity InGaAs/AlGaAs quantum-well laser using a grating coupler monolithically integrated in a selectively disordered waveguide is demonstrated. The laser consists of an amplifier with a narrow channel for lateral single-mode guiding and a tapered section, a grating coupler for output beam collimation and wavelength dispersion, and an external half mirror. Selective quantum-well disordering technique using SiO2 caps of different thicknesses and rapid thermal annealing was employed to reduce the passive waveguide loss in the grating coupler region. Loss reduction from 40 cm-1 to 3 cm-1 was accomplished. Resultant increase of the grating coupler efficiency and expansion of the effective aperture length led to significant improvement of the laser performances. The maximum output power of 105 mW and wide tuning range of 21.1 nm centered at 997 nm were obtained. The well collimated output beam of full diffraction angles at half maximum of 0.16 0.18 was obtained.
Satoru UEHARA Osamu MIZUNO Tohru KIKUNO
In this paper we discuss the estimation of effort needed to update program codes according to given design specification changes. In the Object-Oriented incremental development (OOID), the requirement changes occur frequently and regularly. When a requirement change occurs, a design specification is changed accordingly. Then a program code is updated for given design specification change. In order to construct the development plan dynamically, a simple and fast estimation method of efforts for code updating is strongly required by both developers and managers. However, existing estimation methods cannot be applied to the OOID. We therefore try to propose a straightforward approach to estimate effort for code updating, which reflects the specific properties of the OOID. We list up following factors of the effort estimation for OOID: (1) updating activities consist of creation, deletion, and modification, (2) the target to be updated has four kinds of types (void type, basic type, library type, and custom type), (3) the degree of information hiding is classified into private, protected and public, and (4) the degree of inheritance affects updating efforts. We then propose a new formula E(P,σ) to calculate the efforts needed to update a program P according to a set of design specification changes σ. The formula E(P,σ) includes weighting parameters: Wupd, Wtype, Winf-h and Winht according to the characteristics (1), (2), (3) and (4), respectively. Finally, we conduct experimental evaluations by applying the formula E(P,σ) to actual project data in a certain company. The evaluation results statistically showed the validity of the proposed approach to some extent.
Isamu AKASAKI Satoshi KAMIYAMA Hiroshi AMANO
Breakthroughs in crystal growth and conductivity control of nitride semiconductors during last two decades have led to such developments as high-brightness blue and green light-emitting diodes and long-lived violet laser diodes and so on. All of these nitride-based devices are robust and the most environmentally-friendly ones available. They enable us to save tremendous amount of energy and will be key devices in advanced information technology. Further progress in the area of crystal growth and device engineering will open up new frontier devices based on nitride semiconductors. In this paper, the evolution of nitride-based light-emitting devices is reviewed and the key issues, which must be addressed for nitrides to be fully developed, are discussed.
Hyun-Soo PARK Seihyoung LEE Un-Chul PAEK Youngjoo CHUNG
We will discuss a novel non-contact removal technique of optical fiber coating in continuous and uninterrupted manner with hot air stream. We observed little degradation of the tensile strength of the optical fiber after removing the protective polymer coating and the mean breaking tensile strength of the stripped optical fiber using non-contact removal method was 5.1 GPa.
Hiroyuki OHSAKI Masayuki MURATA
Several gateway-based congestion control mechanisms have been proposed to support an end-to-end congestion control mechanism of TCP (Transmission Control Protocol). One of promising gateway-based congestion control mechanisms is a RED (Random Early Detection) gateway. Although effectiveness of the RED gateway is fully dependent on a choice of control parameters, it has not been fully investigated how to configure its control parameters. In this paper, we analyze the steady state behavior of the RED gateway by explicitly modeling the congestion control mechanism of TCP. We first derive the equilibrium values of the TCP window size and the buffer occupancy of the RED gateway. Also derived are the stability condition and the transient performance index of the network using a control theoretic approach. Numerical examples as well as simulation results are presented to clearly show relations between control parameters and the steady state behavior.
Kenji ITO Shuji TASAKA Yutaka ISHIBASHI
This paper studies effect of packet scheduling algorithms at routers on media synchronization quality in live audio and video transmission by experiment. In the experiment, we deal with four packet scheduling algorithms: First-In First-Out, Priority Queueing, Class-Based Queueing and Weighted Fair Queueing. We assess the synchronization quality of both intra-stream and inter-stream with and without media synchronization control. The paper clarifies the features of each algorithm from a media synchronization point of view. A comparison of the experimental results shows that Weighted Fair Queueing is the most efficient packet scheduling algorithm for continuous media among the four.
Daisuke INOUE Tsutomu MATSUMOTO
Anonymous communication essentially involves two difficulties; 1) How does the sender send a message anonymously? 2) How does the receiver send a reply to the anonymous sender? In this paper, we propose an anonymous communication method named Rivulet that overcomes both of the difficulties by using group communication. Moreover, anonymous communication holds two dilemmas; 1) Strong anonymity or good performance? 2) Protect the privacy or promote the crime? Rivulet provides a solution for the former dilemma. The latter one is hard and important problem for all privacy protection schemes, therefore, we have to keep discussing this dilemma.
Hiroyoshi MIWA Kazunori KUMAGAI Shinya NOGAMI Takeo ABE Hisao YAMAMOTO
The explosive growth of World Wide Web usage is causing a number of performance problems, including slow response times, network congestion, and denial of service. Web site that has a huge number of accesses and requires high quality of services, such as a site offering hosting services, or content delivery services, usually uses a cache server to reduce the load on the original server offering the original content. To increase the throughput of the caching process and to improve service availability, multiple cache servers are often positioned in front of the original server. This requires a switch to direct incoming requests to one of the multiple cache servers. In this paper, we propose a routing algorithm for such a switch in front of clustered multiple cache servers and evaluate its performance by simulation. The results show that our routing algorithm is effective when content has request locality and a short period of validity, for example, news, map data, road traffic data, or weather information. We also identify points to consider when the proposed algorithm is applied to a real system.
An efficient construction of a permutation network has been proposed by Waksman. However, his construction is only for permutation networks with 2k inputs. This paper provides a construction of permutation networks with arbitrary number of inputs that is an extension of Waksman's construction. By applying our construction to Abe's Mix-net, we can improve the efficiency of the Mix-net.
At present, the global Internet consists of many ASes. Each AS pays a pre-determined connection fee to another AS for connecting its network with that AS's network. The connection fee type charging may be rational in case of transferring the best-effort type traffic. However, usage charging is necessary to transferring the resource guaranteed type traffic such as the Intserv traffic and the Diffserv traffic. In this case, each AS pays a per-flow fee to another AS every time it routes a flow into another AS. The per-flow fee paid by each AS becomes a part of the cost for that AS. Thus, each AS needs to select a route with the lowest price to improve its own profit. In this paper, we call such an inter-AS routing scheme a price-based inter-AS routing scheme. When each AS has a request to route an inter-AS flow, it can select an inter-AS route with the lowest price to improve its own profit by this routing scheme. Cost-dependent pricing scheme is suitable for the price-based inter-AS routing scheme because it can reduce frequency of price information exchange between ASes. However, in the cost-dependent pricing scheme, profit in each AS depends on the distribution of path costs in that AS. Generally, ASes with narrow ranges of path costs cannot obtain sufficient profits compared to ASes with wide ranges of path costs. Thus, we propose a routing policy for ASes with narrow ranges of path costs to improve their profits efficiently and evaluate its effect using a simple routing model.
Takashi OKUMA Takeshi KURATA Katsuhiko SAKAUE
In this paper, we describe a method for estimating external camera parameters in real time. We investigated the effectiveness of this method for annotating real scenes with 3-D virtual objects on a wearable computer. The proposed method enables determining known natural feature points of objects through multiplied color histogram matching and template matching. This external-camera-parameter calculation method consists of three algorithms for PnP problems, and it uses each algorithm selectively. We implemented an experimental system based on our method on a wearable vision system. This experimental system can annotate real objects with 3D virtual objects by using the proposed method. The system was implemented in order to enable effective annotation in a mixed-reality environment on a wearable computing system. The system consists of an ultra small CCD camera set at the user's eye, an ultra small display, and a computer. This computer uses the proposed method to determine the camera parameters. It then renders virtual objects based on the camera parameters and synthesizes images on a display. The system works at 10 frames per second.
Deterministic execution testing has been considered a promising way for concurrent program testing because of its ability to replay a program's execution. Since, however, deterministic execution requires that a synchronization event sequence to be replayed be feasible and valid, it is not directly applicable to a situation in which synchronization sequences, being valid but infeasible, are taken into account. Resolving this problem is very important because a program may still meet its specification although the feasibility of all valid sequences is not satisfied. In this paper, we present a new approach to deterministic execution for testing concurrent systems. The proposed approach makes use of the notion of event independence and constructs an automation which accepts all the sequences semantically equivalent to a given event sequence to be replayed. Consequently, we can allow a program to be executed according to event sequences other than the given (possible infeasible) sequence if they can be accepted by the automation.
Tran Ha NGUYEN Kiyohide NAKAUCHI Masato KAWADA Hiroyuki MORIKAWA Tomonori AOYAMA
Layered multicast approach enables IP multicast to adapt to heterogeneous networks. In layered multicast, each layer of a session is sent to separate multicast groups. These layers will be transmitted on the same route, or on different routes. However, traditional congestion control schemes of layered multicast do not consider the case when layers of a session are transmitted on different routes. In this paper, at first we show that in sparse-mode routing protocols like PIM-SM and CBT, layers of a session can be mapped to different Rendezvous Points or cores due to the bootstrap mechanism. It means that layers of a session can be transmitted on different routes. We then show that traditional congestion control schemes of layered multicast do not work properly in sparse-mode routing regions. At last we introduce Rendezvous Point based Layered Multicast (RPLM), a novel congestion control scheme suitable for sparse-mode routing regions, and show that RPLM works efficiently in regions using sparse mode routing protocols. RPLM uses per-RP packet loss rate instead of the overall one to detect congestion on each route, and can react to congestion quickly by dropping the highest layer on the congested route. In addition, RPLM simultaneously drops all the layers those are useless in quality's improvement to prevent bandwidth waste.
This paper treats the data routing problem for fault-tolerant systolic arrays based on Triple Modular Redundancy (TMR) in mixed spatial-temporal domain. The number of logical links required in TMR systolic array is basically 9 times larger than the one for corresponding non-fault-tolerant systolic array. The link sharing is a promising method for reducing the number of physical links, which may, however, degrade the fault tolerance of TMR system. This paper proposes several robust data-routing and resource-sharing (plural data transfers share a physical link, or a data transfer and a computational task share a PE as a relay node for the former and as a processor for the latter), by which certain classes of fault tolerant property will be guaranteed. A stage and a dominated set are introduced to characterize the features of routing/resource-sharing in TMR systems, and conditions on the dominated set and their resultant fault-tolerant properties are derived.
Takeo HAMADA Leif J. BYSTROM Hendrik BERNDT
Surging capacity demand triggered by the increasingly mobile-oriented and exponentially growing Internet has accelerated convergence of networking technologies. In the core network side, IP and photonics have been the two key driving factors of technical innovations. Amid this technical turmoil, Generalized MPLS (GMPLS) in IETF has recently attracted sizable attentions, as it offers potential for "Grand Unification Theory" for network technology convergence. Despite its prospects, however, the proposal is still missing comparable structures in management plane, which is in dire need for carrier-class, reliable operations. Among many industry proposals and standards, TINA vision on connection management architecture (CMA) is the one offering practical and deployable architecture for the converged photonic IP network. TINA IP Control and Management (IPCM) WG was established during TINA phase II (1998-2000), to study IP control and management issues using the architecture basis of TINA-CMA. Latest activities in TINA IPCM WG, compiling experience at Sprint, Telia, Telecom Italia Lab., and Fujitsu, have resulted in a specification for connectivity provider reference points, namely ConS, ConC, and FCon. Use of TINA CMA as building blocks for the IP photonic network convergence is illustrated. An overview of a ConS reference point specification for managed IP connectivity service, named ConS-IPCM, is explained.
We propose an efficient, low cost, multicast ATM switch which is fair to all inputs. The switch consists of a novel copy network which creates unicast packets in a fair manner, followed by a network that routes packets to their correct Address Translation Tables (ATT's) and ultimately a unicast routing network which ensures sequencing. The copy and routing networks are based on deflection routing. We show that our switch requires O(log N) stages and can be designed for any arbitrarily low level of packet loss. The theoretical results are backed up by simulations. Switching elements in both the copying and routing networks have O(1) bit complexity, making the overall bit level hardware complexity of the network O(N log N). The latency of the switch is proportional to the number of stages O(log N). Unlike other existing copy networks, our copy network drops packets in a fair manner and hence can provide quality of service (QoS) support. The switch is output queued and allows the delivery of multiple packets to the same destination during a time slot.
Takashi NORIMATSU Hideaki TAKAGI
The IEEE 1394 is a standard for the high performance serial bus interface. This standard has the isochronous transfer mode that is suitable for real-time applications and the asynchronous transfer mode for delay-insensitive applications. It can be used to construct a small-size local area network. We propose a queueing model for a network with this standard under some assumptions, and calculate the average waiting time of an asynchronous packet in the buffer in the steady state. We give some numerical results, along with validation by simulation, in order to evaluate its performance.
Vikram IYENGAR Hiroshi DATE Makoto SUGIHARA Krishnendu CHAKRABARTY
We present a new technique for hierarchical intellectual property (IP) protection using partially-mergeable cores. The proposed core partitioning technique guarantees 100% protection of critical-IP, while simplifying test generation for the logic that is merged with the system. Since critical-IP is tested using BIST, the controllability and observability of internal lines in the core are enhanced, and test application time is reduced. Case studies using the ISIT-DLX and Picojava processor cores demonstrate the applicability of our technique.
Topological sorting is, given with a directed acyclic graph G=(V,E), to find a total ordering of the vertices such that if (u,v)E then u is ordered before v. Instead of topological sorting, we are interested in how many total orderings exist in a given directed acyclic graph. We call such a total ordering as legal sequence and the problem of finding total number of legal sequences as legal sequence number problem. In this paper, we firstly give necessary definitions and known results obtained in our previous research. Then we give a method how to obtain legal sequence number for a class of directed acyclic graphs, extended 2-b-SPGs. Finally we discuss the complexity of legal sequence number problem for extended 2-b-SPGs.