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.

Towards a collaborative analysis of log data obtained from multiple networks, we first need to clarify what kind of information is available as transferable knowledge between different networks. However, we cannot directly compare net-work log data from different sources because the data largely depends on the network architecture and equipment. In this paper, we focus on relational information among network log events that follow standardized network protocols regardless of network environment. We propose a comparative analysis approach relying on causality between log time-series. In this approach, we classify log messages into anonymized log time-series with log templates, reduce the number of log time-series to decrease processing time, and apply causal discovery with the PC algorithm. To decrease the processing time of causal analysis, we propose a new preprocessing method that reduces the number of log time-series without any domain knowledge (i.e., available in any ISPs). We compare log data obtained from two nation-wide ISPs to demonstrate the effectiveness of the causal approach in comparative analysis.

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

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.

Diagnosis and prevention of anomalous routing states is essential for stable inter-AS (autonomous system) routing management. In particular, the route hijack problem, which is one of the major inter-AS routing-management issues, requires cooperation among multiple ASs for effective detection and prevention. However, this effectiveness highly differs depending on 1) where hijacking and hijacked ASs are located on the AS topology, and 2) what cooperative strategies are used for detecting and filtering hijacking-routes. Because there are no central authority or common framework on the Internet, it is important to analyze the effectiveness of management actions based on cooperative strategies, especially using statistical methods to cope with complex situations. This paper focuses on the analysis and quantification of the effectiveness of cooperative hijack-prevention strategies from the viewpoint of adjacency relations of cooperative ASs. Simulation results that use an actual Internet topology and policy relations demonstrate that simple cooperative strategies organizing selected neighboring ASs into a cluster are sufficiently effective for route-hijack prevention even if only a small part of ASs participate these strategies.

This paper investigates the macroscopic behavior of unwanted traffic (e.g., virus, worm, backscatter of (D)DoS or misconfiguration) passing through the Internet. The data set we used are unwanted packets measured at /18 darknet in Japan from Oct. 2006 to Apr. 2009 that included the recent Conficker outbreak. The traffic behavior is quantified by the entropy of ten packet features (e.g., 5-tuple). Then, we apply PCA (principal component analysis) to a ten dimensional entropy time series matrix to obtain a suitable representation of unwanted traffic. PCA is a well-known and studied method for finding out normal and anomalous behaviors in Internet backbone traffic, however, few studies applied it to darknet traffic. We first demonstrate the high variability nature of the entropy time series for ten packet features. Next, we show that the top four principal components are sufficiently enough to describe the original traffic behavior. In particular, the first component can be interpreted as the type of unwanted traffic (i. e., worm/virus or scanning), and the second one as the difference in communication patterns (e. g., one-to-many or many-to-one). Those two components account for 63.8\% of the original data set in terms of the total variance. On the other hand, the outliers in the higher components indicate the presence of specific anomalies although most of mapped data to the components have less variability. Furthermore, we show that the scatter plot of the first and second principal component scores provides us with a better view of the macroscopic unwanted traffic behavior.

Advanced Layer-3 (L3) switches achieve high-speed IP packet forwarding by storing parts of the header information from transmitted packets into the flow cache in the switch fabric when relaying the IP packets between subnets. When IP traffic is overloaded on an L3 switch, the flow cache is easily exhausted, decreasing the IP packet forwarding performance. Virtual LAN (VLAN), a virtualization technology at the data-link layer, is widely used for the internal networks of many organizations because it allows network configurations to be changed easily and provides design flexibility. In a VLAN-based local area network with multiple L3 switches, the relaying point for each VLAN can be placed on any of the L3 switches. We developed a new network control scheme called distributed virtual routing, which dynamically controls the packet exchange points for each VLAN to suppress the consumption of flow caches. We describe the basic concept and then evaluate the reduction of the relaying flows through the simulation using the real network data.

To manage the changing conditions of the Internet and diagnose the cause of anomalies within it, network operators must obtain and analyze information from network devices such as routers and network monitoring tools. Of that information, route information exchanged by Border Gateway Protocol (BGP) is essential for understanding the Internet at an inter-autonomous-system (AS) level. However, the information is not easily deployed for actual network management because of the enormous amount of the information and the difficulties in manipulating it. To overcome these problems, we propose IM-DB, a network information retrieval system for the interactive analysis and diagnosis of the Internet. Our IM-DB is based on a relational database and can store large amount of network information. By using the IM-DB, network operators can easily search, integrate, and explore information they require. We developed the first version of our IM-DB for storing BGP routing information. The experimental results using this prototype demonstrate the feasibility of our IM-DB.

This paper describes how, in large-scale multi-agent systems, each agent's adaptive selection of peer agents for collaborative tasks affects the overall performance and how this performance varies with the workload of the system and with fluctuations

In this paper, we investigate temporal and spatial correlations of time series of unwanted traffic (i.e., darknet or network telescope traffic) in order to estimate statistical behavior of unwanted activities from a small size of darknet address block. First, from the analysis of long-range dependency, we point out that TCP time series has a weak temporal correlation though UDP time series without huge flooding is well-modeled using a Poisson process. Next, we analyze the spatial correlation between two traffic time series divided by different sized darknet address blocks. We confirm that a TCP SYN traffic time series (e.g, virus or worm) has a clear spatial correlation in the arrival of packets between two neighboring address blocks. Indeed, this spatial correlation remains in traffic time series 1,000 addresses far from the target time series, even if a darknet address block is small (e.g., /26). On the other hand, TCP SYNACK traffic (e.g., backscatter) and UDP traffic (e.g., virus or worm) have less spatial correlation between two adjacent large address blocks. Finally, we estimate the average propagation delay of global unwanted activities appearing in TCP SYN traffic by using the generalized inter-correlation coefficient.

This paper presents personal networks, which integrate a VPN and the per-VPN execution environments of the hosts included in the VPN. The key point is that each execution environment called a portspace is bound to only one VPN, i.e., single-homed. Using this feature of portspaces, personal networks address several problems at multi-homed hosts that use multiple VPNs. Information flow is separated by personal networks so that it is not mixed at multi-homed hosts. IP addressing in a personal network is independent of the other personal networks, even the base network, and therefore does not conflict with those of other networks at multi-homed hosts. In addition, personal networks provide facilities for easy bootstrapping so that the end-users can construct such isolated networks easily. Inheritance of portspaces supports the creation of new portspaces based on existing portspaces. Self-construction of personal networks enables end-users to construct personal networks without help from the base network.

If the Internet is to operate reliably, it is important to verify whether the routing information about an autonomous system (AS) is correctly spread throughout the Internet as the originating AS intends or not. Because the routing information changes as it spreads, it is necessary for the inter-AS diagnostic system to observe the routing information from outside the AS. Each AS is controlled by a single administrative authority based on that AS's own policy, so a cooperative distributed solution is desirable. To cope with these requirements, we have proposed a multi-agent-based inter-AS diagnostic system called ENCORE, where a collection of intelligent agents are located in multiple AS and perform collective observation and analysis. This paper describes its diagnostic functions. It focuses on the agents' autonomous observation actions and their ability to perform cooperative and efficient analysis of routing anomalies. We also discuss the effectiveness and limitations of ENCORE based on analysis of a real AS.