The introduction of optical-circuit-switches (OCSes) has enabled the implementation of capacity- and energy-efficient networks in production datacenters. To correctly operate optical-circuit-switched datacenter networks (OCS DCNs), fibers between pairs of terminals (e.g., servers or top-of-rack switches) and OCSes should be verified before starting operations. However, this task is difficult because OCSes cannot use topology discovery or link monitoring functions, which are only available on electrical packet switches. Motivated by this challenge, we investigated a fiber topology and quality verification (FTQV) problem for OCS DCNs in this paper. Though a previous study inspected fibers in hierarchical OCS DCNs using only one dedicated tester for fiber probing, making the process time-consuming, we consider using digital diagnostic monitoring (DDM) functions at multiple transceivers for fiber inspection. We thus developed solid theories for correctly and quickly inspecting fibers even when multiple probes are sent in parallel. We also developed an algorithm that correctly and quickly solves the FTQV problem on the basis of our theories. Numerical experiments showed that our algorithm completes FTQV at most 48.7 times faster than a baseline algorithm.

Data center networks (DCNs) consisting of optical-circuit switches (OCSes) have been intensively studied due to optical transmission's high capacity and energy efficiency. Since current DCNs consist of packet switches, the condition and cabling of optical fibers can be inspected easily by probing neighboring switches. However, OCS networks cannot be inspected in the same manner because OCSes only pass through optical signals. We have had to attach and detach a tester device to every switch for probing all the fibers, which is very time-consuming. This paper proposes a method for automatically inspecting fibers in an entire DCN without repeating tester reattachment. Our method is based on (1) theories on quickly estimating the fiber condition on the basis of the intensity of received probe signals and involves (2) an algorithm that reduces the number of probes needed. Numerical evaluation showed that our method can be used to inspect a huge DCN with 32,000 fibers in at most 2 days, whereas a baseline method involving repeated tester reattachment would take 2 weeks. An experiment using actual OCSes was also conducted to confirm the feasibility of our method.

The Clos network has been studied for decades as a class of nonblocking switching networks. However, the structure is based on assumptions made at the time of its design, and the assumptions may not remain entirely valid. For instance, an optimal Clos network usually consists of non-square switches (numbers of input and output ports differ), though the switches available today are square ones. In addition, all paths have to be of the same length in Clos networks (presumably to simplify signal setting), but this assumption is no longer valid since signals can be dynamically established nowadays. This paper carefully identifies the implicit assumptions of the Clos network and redesigns it to increase its capacity. Although the conventional Clos network using square switches has to leave several ports unused to realize the nonblocking property, our network has almost no unused ports, which greatly increases network capacity. In addition, our network does not fix the path length and well utilizes shortcut connections if available. Comprehensive theoretical analyses show that our network has a larger capacity than the Clos network under most conditions. Numerical evaluations demonstrate that our network increases the capacity 15% on average and up to 50% at most.

Multi-slot-ahead forecasting on network traffic provides an extra degree of freedom to proactively manipulate the network resources when immediate reconfiguration of networks is expensive or infeasible. In return, it challenges the existing data-driven learning-based approaches on accuracy, especially when considering the evolving property of the traffic process. To this end, we establish an adaptive learning framework for multi-slot-ahead network traffic prediction based on Gaussian Process (GP). GP facilitates learning and comprehending the traffic process from a Bayesian perspective, where the main characteristics can be encoded into the kernel function for performance enhancement. The contributions of this paper are two-fold: 1). To track the evolving traffic characteristics, we approximate the optimal kernel adapting to the current traffic. 2). To predict in a large time horizon without significantly hurt the performance, Linear Model of Co-regionalization (LMC) is utilized to better make use of the correlation among subsequent multiple time-slots. Finally, we demonstrate the high tracking capability as well as the superiority of the proposed framework in terms of prediction accuracy through simulation.

With accurate knowledge of future Channel State Information (CSI), it becomes possible to better comprehend the radio propagating environment and manipulate the wireless resources in a proactive manner, so as to provide solid support to smart and high quality wireless transmission. However, in mobile environment, the evolving correlation patterns in CSI series challenge the existing data-driven algorithms to adaptively learn and predict its behavior. In this article, an adaptive learning algorithm is proposed based on Gaussian Process (GP), to discover and utilize the spatial correlation within a channel and across channels, and produce accurate CSI prediction. Specifically, 1). To track the evolving correlation of a channel, we tailor Spectrum Mixture (SM) kernel to not only approximate the optimal kernel adapting to the current CSI, but also capture the combined effect of path loss and User Equipment (UE) motion. 2). The correlation across channels is encoded into the GP-based learning framework through Linear Model of Co-regionalization (LMC). Finally, we verify the performance improvements through simulation.

Clos networks are widely used as an efficient physical structure due to their nonblocking property. However, in strictly nonblocking networks composed of ordinary optical switches (switches with equal numbers of input/output ports), we find that a substantial fraction of ports can remain unused, which decreases the efficiency of Clos networks. This inefficiency comes from the implicit restriction that the two ''sides'' of switches have distinct roles, i.e., ports on one side are connected to endpoints (terminals) while those on the other side are linked to switches. Removing this restriction brings greater freedom in structuring the network and can increase the capacity without losing the strictly nonblocking property. This paper proposes a new physical structure and provides several theorems that address network capacity. Numerical experiments show that our structure increases the capacity by up to about 30%.

Traffic matrix (TM) estimation has been extensively studied for decades. Although conventional estimation techniques assume that traffic volumes are unchanged between origins and destinations, packets are often discarded on a path due to traffic burstiness, silent failures, etc. This paper proposes a novel TM estimation method that works correctly even under packet drops. The method is established on a Boolean fault localization technique; the technique requires fewer counters though it only determines whether each link is healthy. This paper extends the Boolean technique so as to deal with traffic volumes with error bounds just by a small number of counters. Along with submodular optimization for the minimum counter placement, we evaluate our method with real network datasets.

Modern networks have complex configurations to provide advanced functions. Network softwarization, a promising new movement in the networking community, could make networks more complexly configured due to the nature of software. Since these complexities make the networks error-prone, network verification is attracting attention as a key technology to detect inconsistencies between a configuration and an operational policy. Existing verifiers are, unfortunately, either inefficient or incomplete (operational policies are not rigorously checked). This paper presents a novel framework of data-plane verification. So as to efficiently manage the large search space defined by packet headers, our framework formalizes the consistency check by applying simple set operations defined in a small quotient space of packet header. This paper also reveals that the two spaces can be connected via the windowing query in computational geometry. Two windowing algorithms are proposed and backed by solid theoretical analyses. Experiments on real network datasets show that our framework with the windowing algorithms is surprisingly fast; when verifying policy compliance in a real network with thousands of switches, our framework reduces the verification time of all-pairs reachability from ten hours to ten minutes.

Network verification is attracting attention as a key technology to detect configuration errors before deploying the network. In verification, a set of packets to be inspected is usually specified by a window -- a multi-dimensional rectangle defined by packet header fields (e.g., address prefixes and port ranges). Network operators have to know the forwarding behaviors of packets inside the window, this can be regarded as the windowing query problem in computation geometry. This paper proposes a novel windowing algorithm for network verification. Unlike existing windowing algorithms, our algorithm runs on a compressed data structure, because the search space has to be represented in a compressed form due to the space complexity.

Modern networks have complex configurations to provide advanced functions, but the complexity also makes them error-prone. Network verification is attracting attention as a key technology to detect inconsistencies between a configuration and a policy before deployment. Existing verifiers, however, either generally verify various properties over the policy at the cost of efficiency, or efficiently perform configuration analysis without paying much attention to the policy. This paper presents a novel framework of data-plane verification, which flexibly checks the inconsistency with great efficiency. For the purpose of generality, our framework formalizes a verification process with three abstract steps: each step is related to 1) packet behaviors defined by a configuration, 2) operator intentions described in a policy, and 3) the inspection of their relation. These steps work efficiently with each other on the simple quotient set of packet headers. This paper also reveals how the second step can be regarded as the windowing query problem in computational geometry. Two novel windowing algorithms are proposed with solid theoretical analyses. Experiments on real network datasets show that our framework with the windowing algorithms is surprisingly fast even when verifying the policy compliance; e.g., in a medium-scale network with thousands of switches, our framework reduces the verification time of all-pairs reachability from ten hours to ten minutes.

Virtual network embedding has been intensively studied for a decade. The time complexity of most conventional methods has been reduced to the cube of the number of links. Since customers are likely to request a dense virtual network that connects every node pair directly (|E| = O(|V|2)) based on a traffic matrix, the time complexity is actually O(|E|3 = |V|6). If we were allowed to reduce this dense network into a sparse one before embedding, the time complexity could be decreased to O(|V|3); the time gap can be a million times for |V| = 100. The network reduction, however, combines several virtual links into a broader link, which makes the embedding cost (solution quality) much worse. This paper analytically and empirically investigates the trade-off between the embedding time and cost for the virtual network reduction. We define two simple reduction algorithms and analyze them with several interesting theorems. The analysis indicates that the embedding cost increases only linearly with exponential decay of embedding time. Thorough numerical evaluation justifies the desirability of the trade-off.

Building optimal virtual networks across multiple domains is an essential technology for offering flexible network services. However, existing research is founded on an unrealistic assumption: providers will share their private information including resource costs. Providers, as well known, never actually do that so as to remain competitive. Secure multi-party computation, a computational technique based on cryptography, can be used to secure optimization, but it is too time consuming. This paper presents a novel method that can optimize virtual networks built over multiple domains efficiently without revealing any private information. Our method employs secure multi-party computation only for masking sensitive values; it can optimize virtual networks under limited information without applying any time-consuming techniques. It is solidly based on the theory of optimality and is assured of finding reasonably optimal solutions. Experiments show that our method is fast and optimal in practice, even though it conceals private information; it finds near optimal solutions in just a few minutes for large virtual networks with tens of nodes. This is the first work that can be implemented in practice for building optimal virtual networks across multiple domains.

The routing efficiency of structured overlay networks depends on the consistency of pointers between nodes. This consistency can, however, break temporarily when some overlay nodes fail, since it takes time to repair the broken pointers in a distributed manner. Conventional solutions utilize "backpointers" to quickly know the failure among the pointing nodes, which allows them to fix the pointers in a short time. Overlay nodes are, however, required to maintain backpointers for every pointing node which incurs significant consistency check and memory overheads. This paper proposes a novel light-weight protocol; an overlay node gives a "testament" containing its acquaintances (backpointers) only to its successor (i.e., clockwise closest node), and other nodes are freed from maintaining it. Our carefully-designed protocol guarantees that all acquaintances are registered with the testament even in the presence of churn, and the successor notifies the acquaintances for the deceased. Even if the successor passes away and the testament is lost, the successor of the successor can identify the acquaintances at a high success ratio. Simulations show that our protocol greatly reduces the mean time to repair (MTTR) and memory overheads while messaging cost increases.

Building optimal virtual networks across multiple domains is an essential technology to offer flexible network services. However, existing research is founded on an unrealistic assumption; providers will share their private information including resource costs. Providers, as is well known, never actually do that to remain competitive. Technically, secure multiparty computation, which is a computational technique based on the cryptography, can be used to secure optimization, but it is too time-consuming. This paper presents a novel method to optimize virtual networks built over multiple domains, with great efficiency but without revealing any private information. Our method employs secure multi-party computation but only for masking sensitive values; it can optimize virtual networks under limited information without any time-consuming technique. It is solidly based on the theory of optimality, and is assured of finding reasonably optimal solutions. Experiments show that our method is fast and optimal in practice even concealing private information; it finds nearly optimal solutions in just a few minutes for large virtual networks with tens of nodes. This is the first work that can be implemented in practice for building optimal virtual networks across multiple domains.

In software-defined networking, applications are allowed to access a global view of the network so as to provide sophisticated functionalities, such as quality-oriented service delivery, automatic fault localization, and network verification. All of these functionalities commonly rely on a well-studied technology, packet classification. Unlike the conventional classification problem to search for the action taken at a single switch, the global network view requires to identify the network-wide behavior of the packet, which is defined as a combination of switch actions. Conventional classification methods, however, fail to well support network-wide behaviors, since the search space is complicatedly partitioned due to the combinations. This paper proposes a novel packet classification method that efficiently supports network-wide packet behaviors. Our method utilizes a compressed data structure named the multi-valued decision diagram, allowing it to manipulate the complex search space with several algorithms. Through detailed analysis, we optimize the classification performance as well as the construction of decision diagrams. Experiments with real network datasets show that our method identifies the packet behavior at 20.1 Mpps on a single CPU core with only 8.4 MB memory, by contrast, conventional methods failed to work even with 16 GB memory. We believe that our method is essential for realizing advanced applications that can fully leverage the potential of software defined networking.

A distributed hash table (DHT) network can be used for many distributed services and systems. In DHT networks, it takes logN look-up steps to search for required data where N is the number of nodes. However, the look-up process is redundant in the IP network because each look-up process generates a lot of communication among nodes. In massive data management such as sensor and web information management, this results in high network load even if each the search process takes only logN look-up steps. To solve this problem, we propose an efficient query bundling mechanism that makes it possible to bundle multiple queries by using range information. Range information consists of ID space information kept by a node. When a source node receives range information from a destination node, the source node matches all queries for the range information and forwards queries matching the range information to the destination node directly. This effectively reduces the number of look-up processes and the network load for the IP network. In addition, our mechanism can be implemented into conventional DHT networks and can easily be combined to effective DHT routing algorithms such as Chord, Kademlia, and Pastry. In evaluation, we implement our mechanism into DHT networks and compare its performance with that of conventional query bundling mechanisms. The results show that our mechanism reduces by up to 75% the total number of forwarding operations to put data compared with other mechanisms. In addition, our mechanism realizes the reduction of the number of forwarding operations per look-up process by up to 85% compared to other mechanisms.

In this paper, we propose an efficient video streaming server management scheme for streaming service that minimizes power consumption while satisfying client's requests. In conventional schemes, the power minimizing policy is calculated by means of simple dynamic programming or linear programing systems. However, these schemes may suffer changing the power minimizing policy substantially when the client's requests change even slightly. This increases the cost of changing streaming servers. On the other hand, our approach minimizes power consumption while satisfying client's requests by considering the number of times the policy is changed. To reduce the number of changes, our scheme uses dynamic programming by considering trends in client's requests and the stream length for each server. Evaluations shows that our scheme reduces power consumption by up to 35%-45% of conventional schemes.