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.

Configuring network devices is a main task of network operators. However, understanding and consistently updating network configuration files (config) is not an easy task especially in a large-scale and complicated networks. In this paper, we propose a semantic approach to provide better understanding of such config files, different from syntax based approaches. The key idea of the work is to extract semantics of blocks of the config files by document embedding techniques in NLP. This extraction enables us to understand context of config blocks with semantic similarity metrics instead of syntax similarity ones. Furthermore, this approach can be naturally extended to additional technical documents such as vendor’s manual documents to add more specific information on the semantics of configs. We first discuss the quality of the obtained semantics for several embedding techniques, by using clustering evaluations. We next demonstrate the effectiveness of our approach with two case studies with real network configs: (1) similar config block detection and (2) automatic labeling of config block with vendor’s documents.

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%.

In this paper, we've explored the possibility of expecting/avoiding degradation of network service performance of Network function virtualization (NFV) by long-term monitoring of hardware and network performances, and adjusting resource assignments of VNFs by preventive management based on Neural Networks (NNs). We've constructed an experimental network service, periodically inserted the specific amount of stresses to the hardware and networks systems, and let the NN learn the long-term trends of service performance changes, then try to adjust VNF resource assignment based on NN's expectations. We evaluate and discuss the results of our experiments.

Recently, network operators are confronting the challenge of exploding traffic and more complex network environments due to the increasing number of access terminals having various requirements for delay and package loss rate. However, traditional routing methods based on the maximum or minimum single metric value aim at improving the network quality of only one aspect, which makes them become incapable to deal with the increasingly complicated network traffic. Considering the improvement of deep learning techniques in recent years, in this paper, we propose a smart packet routing strategy with Tensor-based Deep Belief Architectures (TDBAs) that considers multiple parameters of network traffic. For better modeling the data in TDBAs, we use the tensors to represent the units in every layer as well as the weights and biases. The proposed TDBAs can be trained to predict the whole paths for every edge router. Simulation results demonstrate that our proposal outperforms the conventional Open Shortest Path First (OSPF) protocol in terms of overall packet loss rate and average delay per hop.

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.

Recent years, Software Defined Routers (SDRs) (programmable routers) have emerged as a viable solution to provide a cost-effective packet processing platform with easy extensibility and programmability. Multi-core platforms significantly promote SDRs' parallel computing capacities, enabling them to adopt artificial intelligent techniques, i.e., deep learning, to manage routing paths. In this paper, we explore new opportunities in packet processing with deep learning to inexpensively shift the computing needs from rule-based route computation to deep learning based route estimation for high-throughput packet processing. Even though deep learning techniques have been extensively exploited in various computing areas, researchers have, to date, not been able to effectively utilize deep learning based route computation for high-speed core networks. We envision a supervised deep learning system to construct the routing tables and show how the proposed method can be integrated with programmable routers using both Central Processing Units (CPUs) and Graphics Processing Units (GPUs). We demonstrate how our uniquely characterized input and output traffic patterns can enhance the route computation of the deep learning based SDRs through both analysis and extensive computer simulations. In particular, the simulation results demonstrate that our proposal outperforms the benchmark method in terms of delay, throughput, and signaling overhead.

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.

Wireless communication devices have spread widely in our society. However, they usually depend heavily on communication infrastructure, leaving them vulnerable to disasters or congestion of base stations. In these situations, a method to send out data without the support of infrastructure is required. Data transmission by D2D communication is a reliable method that does not rely on infrastructure. In this paper, we aim to improve the data dissemination using D2D transmission by applying the concept of assigning “modes” to devices according to their own mobility. In our study, we assume a multi-channel environment, where devices will be allocated different amounts of frequency channels according to their modes. We propose a mode selection function that uses velocity information of the devices to assign modes. By using this function, it is possible to allocate more frequency channels to devices of high mobility, so that they can transmit their data to more devices as they move through a wide area. By mathematical analysis, we evaluate the fairness of disseminated data density among devices of various velocities and the obtained results indicate the effectiveness of the proposed method for improving the efficiency of data dissemination.

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.

There are many applications which cannot be executed by mobile devices due to their limitations in memory, processing, battery, among others. One solution to this would be offloading heavy tasks to cloud servers in the edge of the network, in a service model called Edge Cloud Computing. The main Quality of Service requirement of this model is a low Service Delay, which can be achieved by lowering Transmission Delay and Processing Delay. Works in literature focus on either one of those two types of delay. This paper, however, argues that an approach which combines transmission and processing technologies to lower Service Delay would be more efficient. This idea is defended by an analysis of the service model and existing stochastic modeling of the Edge Cloud Computing system. We conclude that a dual focus approach would be the only way of truly minimizing the Service Delay, therefore being the desired method to improve Quality of Service. We conclude by laying the foundation for a future model that follows such concept.

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.

Many studies have focused on developing Transmission Control Protocol (TCP) flow control mechanisms to enable more effective use of bandwidth in data center networks. However, the studies cannot achieve total optimization of bandwidth use for data center networks. This is because they do not take into account the path design of TCP flows and the hierarchical structure in data center networks through which TCP flows. To address this issue, we propose a TCP flow control mechanism for effectively using bandwidth by dynamically controlling paths through which TCP flows. To achieve this dynamic control, a hierarchical feedback model is used to obtain an optimal path establishment policy. With the model, all network components exchange their resource states with each other when each network component establishes a TCP flow. This enables each network component to learn the best TCP flow path for effective bandwidth use. An evaluation process shows that the mechanism achieves more effective bandwidth use and more efficient flow control than the conventional TCP flow control.