Efficient probabilistic decision trees are required in various application areas such as character recognition. This paper presents a polynomial-time approximate algorithm for designing a probabilistic decision tree. The obtained tree is near-optimal for the cost, defined as the weighted sum of the expected test execution time and expected loss. The algorithm is advantageous over other reported heuristics from the viewpoint that the goodness of the solution is theoretically guaranteed. That is, the relative deviation of the obtained tree cost from the exact optimum is not more than a positive constant ε, which can be set arbitrarily small. When the given loss function is Hamming metric, the time efficiency is further improved by using the information theoretical lower bound on the tree cost. The time efficiency of the algorithm and the accuracy of the solutions were evaluated through computational experiments. The results show that the computing time increases very slowly with an increase in problem size and the relative error of the obtained solution is much less than the upper bound ε for most problems.

Real-world IP networks are heterogeneous in terms of server and link capacities. A sophisticated and comprehensive load balancing method is essential if we are to avoid congestion in the servers and links of heterogeneous networks. If such a method is not available, network throughput is limited by bottleneck servers or links. This paper proposes an anycast technique that achieves load balancing under heterogeneity. The proposed method well suits implementation on active networks. By taking advantage of the processing ability provided by active nodes, the method can decide packet routes flexibly on the basis of various criteria to realize a variety of load balancing schemes. Some of these schemes can successfully prevent the congestion of heterogeneous networks by tackling bottlenecks in both server and link capacities. The method is also advantageous given its light control load even when using many mirrored servers. Computer simulations confirm the effectiveness of these features.

VP Network Designer, a software tool that automates the tasks involved in the transaction of service orders in VP leased line services, is introduced here in this paper. The tool is composed of two functions: VP Design Explorer which, given a request for VP establishment, determines a disjoint backup and target VP routes to support fault tolerance under VP-APS scheme; Network Resource Administrator which provides data administering functions, useful in maintaining a clear insight into the state of the network. The paper focuses on the implementation of VP Design Explorer. A scheme, proposed as disjoint VP routes search, is used to evaluate a pair of VP routes that guarantee duct level independence. The scheme is based on an integer programming modeling approach, and is proved to be effective for evaluating disjoint paths in a hierarchical network. VP Design Explorer is equipped with an additional feature where, under conditions of resource shortage, it presents a set of additional resources that are necessary to satisfy VP demand, together with the VP routes that become possible by the additions. Formulation of the problem is attained through an extension of the disjoint VP routes search scheme. A prototype of VP Network Designer is presented and its performance tested using computer simulations. The tool is found to achieve a computational time performance in the order of seconds and minutes, for evaluating disjoint VP routes search problems under real life ATM network conditions.

This paper proposes a new self-healing scheme that differentiates the bandwidth requirement for each network service on ATM networks. First, we show the necessity of our proposed scheme. In the future network, we must satisfy two demands, rapid restoration from failure and differentiated bandwidth requirements. The conventional restoration scheme, called the self-healing scheme, realizes rapid restoration, but does not support bandwidth differentiation; the new self-healing scheme proposed herein does. We also show that the proposed scheme reduces the spare resources required for backup. The scheme can be realized as a simple extension of the conventional self-healing scheme. Finally, simulations show that the proposed scheme requires fewer spare resources while offering comparable restoration time to the conventional approach against any demand pattern.

Performance measurements are indispensable for managing the Internet. Among the performance measurement techniques known, passive measurement is attractive because of its accuracy; user traffic is observed without inserting additional test traffic. However, the technique is handicapped by its large storage and bandwidth costs. This paper proposes a passive packet loss measurement technique that effectively avoids the difficulty of the conventional passive measurement approaches. Its key advance is utilizing the packet feature computed by a hash function. Since the feature can identify a packet with a short length of data, it becomes possible to greatly decrease the storage and bandwidth costs of passive measurements. The paper details the measurement procedure and assesses the design parameters used in the method. In addition, the validity of the proposed method is confirmed through experiments. The experiments also show the advantage of the method over the conventional active measurement.

Telecommunication technologies are making relentless progress. In this circumstance, network cost must be evaluated to assess the effectiveness of emerging technologies. To do such an evaluation efficiently, it is necessary to develop a software tool that can calculate the network cost independent of the employed technologies. This paper describes computational techniques used in developing such a software tool. First, the functional requirements are identified to establish a flexible tool that is applicable to a wide range of technologies. One of the required functions is the function that computes the resource amount and the network cost from the given conditions such as traffic demands, a cable duct network, multiplex hierarchy and the specifications of network elements employed. As this computing function, the paper proposes an appropriate path classification scheme that enables us to evaluate the resource amount correctly when a service protection technique is applied to the target network. Namely, the proposed scheme yields evaluations that isolate the primary path route from the backup path route. This isolation is not always provided without classification. In addition, a classification of network elements is also derived for valid estimation of the necessary interface board number, which is a basis of estimating the required network element amount. This classification allows us to identify the exact points of path cross-connection and termination, which affects the number of interface boards. This paper presents the computing procedures that realize path grouping and an estimation of network elements using these classification schemes. Finally, the paper describes a prototype of the tool to confirm the feasibility and effectiveness of the proposed schemes.

Decision tree design is an important issue because decision trees have many applications in, for example, fault diagnosis and character recognition. This paper describes an algorithm designing a probabilistic decision tree, in which a test applied to a state produces different outcomes with non-zero probability. The algorithm strictly minimizes the tree cost, which is defined as the weighted sum of expected loss and expected test execution time. The lower bound of the cost is utillized to remove the excessive computing time needed to search for the exact optimum. This lower bound is derived from information theory and is transformed to an easily computable representation by introducing a network model. The result of a computational experiment confirms the time efficiency of the proposed method.

Time synchronization is indispensable for wide area distributed systems including sensor networks, automation systems, and measurement/control systems. Another application is clock distribution, which is indispensable to support continuous information transfer. Because of the increasing demand for more sophisticated applications, it is essential to establish a time synchronization technique that offers higher accuracy and reliability. Particularly, the accuracy of time synchronization for Ethernet must be enhanced since Ethernet is becoming more important in telecommunication networks. This paper investigates a precise time synchronization technique that supports Gb/s Ethernet. To obtain accurate time synchronization, delay variation in message transfer and processing must be minimized. For this purpose, the paper first describes the implementation of preemptive priority queuing, which decreases the message delay variation of Ethernet. Through experiments, it is shown that preemptive priority queuing effectively achieves very low delay variation. The paper then proposes a method to synchronize the time signal of a slave node to that of the master node. The proposed time synchronization method is performed in the lower protocol layer and implemented on FPGA-based hardware. The method achieves superior time accuracy through the low message transfer/processing delay variation provided by preemptive priority, lower layer execution, and hardware implementation. The effectiveness of the method is confirmed through experiments. The experiments show that the time variation achieved by the method is smaller than 0.1 µsec. This performance is better than those obtained by existing synchronization methods.

Asynchronous Transfer Mode (ATM) is an information transport technique that well supports Broadband ISDN (B-ISDN). One unsolved problem to the perfection of ATM networks is to provide a testing environment that conforms to some standardized network management scheme. From this point of view, remotely controlled virtual path testing is considered in this paper. Remotely controlled virtual path testing should be executed through the standardized Telecommunications Management Network (TMN) model, which employs the OSI systems management concept as the basis of information exchange. Thus, this paper addresses the two issues that arise when OSI systems management standards are applied to virtual path testing. One issue is to define relevant information models. The other issue is to provide test resources with a concurrency control mechanism that guarantees a consistent test environment without causing deadlocks. To resolve these issues, technical requirements are clarified for the remote control of test resources. Next, alternatives to the concurrency control mechanism are shown and compared through computer simulations. A method of defining information models is then proposed. The proposed method ensures the easy storage and retrieval of intermediate test results as well as permitting the effective provision of concurrency control for test resources. An application scenario is also derived. The scenario shows that tests can be executed by using standardized communication services. These results confirm that virtual path testing can be successfully achieved in conformance with the OSI systems management standards.