We propose an algorithm for finding heavy hitters in terms of cardinality (the number of distinct items in a set) in massive traffic data using a small amount of memory. Examples of such cardinality heavy-hitters are hosts that send large numbers of flows, or hosts that communicate with large numbers of other hosts. Finding these hosts is crucial to the provision of good communication quality because they significantly affect the communications of other hosts via either malicious activities such as worm scans, spam distribution, or botnet control or normal activities such as being a member of a flash crowd or performing peer-to-peer (P2P) communication. To precisely determine the cardinality of a host we need tables of previously seen items for each host (e.g., flow tables for every host) and this may infeasible for a high-speed environment with a massive amount of traffic. In this paper, we use a cardinality estimation algorithm that does not require these tables but needs only a little information called the cardinality summary. This is made possible by relaxing the goal from exact counting to estimation of cardinality. In addition, we propose an algorithm that does not need to maintain the cardinality summary for each host, but only for partitioned addresses of a host. As a result, the required number of tables can be significantly decreased. We evaluated our algorithm using actual backbone traffic data to find the heavy-hitters in the number of flows and estimate the number of these flows. We found that while the accuracy degraded when estimating for hosts with few flows, the algorithm could accurately find the top-100 hosts in terms of the number of flows using a limited-sized memory. In addition, we found that the number of tables required to achieve a pre-defined accuracy increased logarithmically with respect to the total number of hosts, which indicates that our method is applicable for large traffic data for a very large number of hosts. We also introduce an application of our algorithm to anomaly detection. With actual traffic data, our method could successfully detect a sudden network scan.

When communication network planning-design is performed, especially in a short-term case, it is important to utilize existing facilities in the construction of the new network. In this paper, link capacity assignment problem (CA problem) for packet-switched networks is investigated with the consideration of the existing network. To deal with this, per-unit cost of existing link capacity is thought to be less than that of newly installed capacity and a link cost function is modeled by a non-linear, non-differentiable one which is composed of two portions of capacity cost. After formulating the CA problem, two optimum algorithms derived from Lagrange multiplier method are presented and a modified algorithm is used for solving the CA problem in order to reduce the computation time. Some numerical results show that according to the values of link traffic flows, there will be links whose capacities must be set equally to the existing values. Moreover, when link cost difference is introduced in the CA problem, the number of links that the capacities of which have to be changed from existing values is less than that of linear cost function case, i.e., the case without consideration of the cost difference in link capacity.

Climate change and/or pandemics are global life threatening concerns. For verifying and utilizing monitored data for solving to the Climate Change concerns, a network system based on device ID would be proposed. In this paper, we review the recent standardization initiatives in ITU-T, and propose an ID network that can be used to verify the solutions.

Automatic location identification is required for emergency calls in Japan and many other countries. However, promptly providing a reliable position is a problem in places where the global positioning system (GPS) signal is extremely weak. We propose an acquisition scheme for the assisted GPS (AGPS) architecture based on a timing-synchronized mobile network. System errors as well as code uncertainty range and frequency uncertainty range are discussed. With this method, the acquisition search range is significantly reduced, and a long-time coherent correlation is made possible. Simulations and experiments prove that the method is fast, efficient and power-saving for the user handset. Furthermore, the AGPS receiver can perform a short TTFF (Time To First Fix) start even with no ephemeris kept in the handset.

The bandwidth explosion ushered in by the popularity of the Internet has spurred the recent acceleration in the development and deployment of equipment supporting packet based broadband services. This coupled with the widespread deployment of WDM based Optical Transport Systems in the core network to satisfy the corresponding increase in capacity demand, has led network planners for tighter coordination between IP and Optical layers to increase reliability, robustness of next generation backbone network. In this paper, we propose a solution known as border model, which is tailored to address deployment concerns associated with GMPLS technology in existing networks. We extend our proposal to include, "Border model based Multi-layer service network architecture," to provide coordinated multi-layer IP and Optical services, for different network design scenarios. Resource Control is an important aspect of multi-layer service networks. This paper examines next generation requirements for resource control, defines resource control architecture and presents some evaluation results for multi-layer recovery techniques in the context of Multi-layer service network based on border model.

We have developed a new traffic measuring tool and applied it to the real-time simulation of a network. It monitors IP traffic on an ATM link and continuously transfers the length and timestamp of each IP packet to a post-processing system. The post-processing system receives the data, estimates the cell's arrival epoch at the transmission queue of the ATM link, and simulates the queueing behavior on-line if conditions differ from those of the actual system. The measuring tool and real-time simulation represent a new approach to traffic engineering. A new estimation problem, the arrival sequence estimation, is shown and some algorithms are proposed and evaluated. Also, a new dimensioning algorithm called the queue decay parameter method, which is expected to be robust and applicable to real-time control, is proposed and evaluated.

Optical signal processing is one of essential technologies for improving the flexibility of all-optical network. Above all, recently there have been a lot of studies regarding all-optical 2R/3R regeneration technology. However, there are few studies about all-optical 2R/3R technologies that are carried out in field environment. In this paper, we report the successful results of field trials of an all-optical 2R regeneration system based on an electro-absorption modulator for 40-Gbit/s WDM transmission systems with optical add/drop multiplexing. It was made sure that by applying the all-optical 2R regeneration system to the optical add/drop multiplexer in the 320-km-long transmission systems the transmission characteristics of the express signal after 320-km transmission and those of the dropped signal at 160-km can be made nearly the same. It is quite important that the transmission characteristics are equal for both the dropped and express channel from a point of view of the system design, and the results in this paper suggests one possible solution for this matter.

This paper presents a realization of our IP based realtime VLBI (Very Long Baseline Interferometer) observation testbed with the highest sensitivity in the world. Today's rapid deployment of high-speed wide area networks will give a major breakthrough in VLBI astronomy in terms of its observational sensitivity and immediateness. VLBI requires huge amount of data transfer from several radio telescopes located separately each other for calculating cross-correlation. High-speed networks can be applied to such data transfer instead of conventional magnetical tape recording and physical transportation, which cause a serious performance bottleneck. We have newly designed and implemented a special component named gigabit network access node, which can exchange 2.048 Gbps telescope data through a 2.488 Gbps OC-48c/STM-16c SONET/SDH link. We have also constructed the world's first multi-gigabit-rate VLBI observation testbed using actual high-speed wide area optical networks and successfully conducted several real observations.

The rapidly increasing bandwidth requirements of IP traffic mean that networks based on optical technologies in conjunction with IP routing technologies will provide the backbone of the next generation Internet. One of the major issues is how to construct an optical-technology-based backbone network that offers the economical transport of large-scale IP/MPLS services while achieving reliable, robust network. The key to achieving this objective lies in multilayer coordination technologies using Multi-Layer Service Network [MLSN] Architecture, that we previously proposed [2]. One of the important aspects of MLSN architecture is ability to effectively use GMPLS network resources by IP/MPLS service networks. We propose extensions to previously proposed MLSN architecture. The proposed extensions to MLSN architecture are tailored to address "service virtualization and separation" of various service networks over GMPLS backbone. As a part of this extended MLSN architecture, we introduce novel concepts known as Logical Router (LR) and Virtual Router (VR) that would enable border router to be services domain router, so that it can connect multiple service networks such as L2VPN, L3VPN etc., over GMPLS backbone by offering service separation or virtualization. This service separation/isolation greatly enhances the reliability of next generation networks, as any failure on one service should be isolated from others. We evaluate our extended network architecture against requirements for the large scale network targeting at introducing such new technology to cope with vast traffic explosion and challenges in operation and service provision sophistication.

We quantitatively evaluate how sampling and spatio/temporal granularity in traffic monitoring affect the detectability of anomalous traffic. Those parameters also affect the monitoring burden, so network operators face a trade-off between the monitoring burden and detectability and need to know which are the optimal paramter values. We derive equations to calculate the false positive ratio and false negative ratio for given values of the sampling rate, granularity, statistics of normal traffic, and volume of anomalies to be detected. Specifically, assuming that the normal traffic has a Gaussian distribution, which is parameterized by its mean and standard deviation, we analyze how sampling and monitoring granularity change these distribution parameters. This analysis is based on observation of the backbone traffic, which exhibits spatially uncorrelated and temporally long-range dependence. Then we derive the equations for detectability. With those equations, we can answer the practical questions that arise in actual network operations: what sampling rate to set to find the given volume of anomaly, or, if the sampling is too high for actual operation, what granularity is optimal to find the anomaly for a given lower limit of sampling rate.

This paper addresses the optimum routing problem of multipoint connection in large-scale networks. A number of algorithms for routing of multipoint connection have been studied so far, most of them, however, assume the availability of complete network information. Herein, we study the problem under the condition that only partial information is available to routing nodes and that routing decision is carried out in a distributed cooperative manner. We consider the network being partitioned into clusters and propose a cluster-based routing approach for multipoint connection. Some basic principles for network clustering are discussed first. Next, the original multipoint routing problem is defined and is divided into two types of subproblems. The global optimum multicast tree then can be obtained asymptotically by solving the subproblems one after another iteratively. We propose an algorithm and evaluate it with computer simulations. By measuring the running time of the algorithm and the optimality of resultant multicast tree, we show analysis on the convergent property with varying network cluster sizes, multicast group sizes and network sizes. The presented approach has two main characteristics, 1) it can yield asymptotical optimum solutions for the routing of multipoint connection, and 2) the routing decisions can be made in the environment where only partial information is available to routing nodes.

This paper studies the routing algorithms for multi-destination connections where each destination may require different amount of data streams. This asymmetric feature can arise mostly in a large and/or heterogeneous network environment. There are mainly two reasons for this. One is that terminal equipments may have different capabilities. The other is that users may have various interests in the same set of information. We first define the asymmetric multicast problem and describe an original routing method for this type of multicast. The method is then employed in the presented routing algorithms, which can be run in multi-cluster environment. The multi-cluster architecture is considered to be effective for running routing in the networks, where a variety of operating methods might be applied in different clusters but global network performance is required. Our algorithms are designed based on some classical Steiner tree heuristics. The basic goal of our algorithms is to make routing decisions for the asymmetric multicast connections with minimum-cost purpose. In addition, we also consider delay constraint requirements in the multicast connections and propose correspondent algorithms. We compare the performance between SPT (Shortest Path Tree)-based algorithms and the presented algorithms by simulations. We show that performance difference exists among the different types of the algorithms.

In this paper, we propose a method of detecting TCP performance degradation using only bottleneck-link utilization statistics: mean and variance. The variance of link utilization normally increases as the mean link-utilization increases. However, because link-utilization has a maximum of 100%, as the mean approaches 100%, the possible range of fluctuation becomes narrow and the variance decreases to zero. In this paper, using the M/G/R processor sharing model, we relate this phenomenon to the behavior of flows. We also show that by using this relationship, we can detect TCP performance degradation using the mean and variance of link utilization. In particular, this method enables a network operator to determine whether or not the degradation originates from the congestion of his/her own network. Because our method requires us to measure only link utilization, the cost of performance management can be greatly decreased compared with the conventional method, which requires dedicated functions for directly measuring the TCP performance.

A new rate-controlled queueing discipline, called virtual rate-based queueing (VRBQ), is proposed for packet-switching nodes in connection-oriented, high-speed, wide-area networks. The VRBQ discipline is based on the virtual rate which has a value between the average and peak transmission rates. By choosing appropriate virtual rates, various requirements can be met regarding the performance and quality of services in integrated-service networks. As the worst-case performance guarantee, we determine the upper bounds of queueing delay when VRBQ is combined with an admission control mechanism, i.e., Dynamic Time Windows or Leaky Bucket. Simulation results demonstrate the fairness policy of VRBQ in comparison with other queueing disciplines, and the performance of sources controlled under different virtual rates.