Network verification has been proposed to help network operators eliminate the outage or security issues caused by misconfigurations. Recent studies have proposed SMT-based approaches to verify network properties with respect to network configurations. These approaches translate the verification problem into a Satisfiability Module Theories (SMT) problem. Although these approaches are attractive because of their broad coverage, they can scale to moderate-size networks only. In this paper, we propose BiNode to accelerate the network verification process. The key idea is to formulate the SMT constraints in a manner that reduces/eliminates the cyclic dependencies between its variables. By doing so, we expedite the solving of the SMT problem. We implement and evaluate the performance of BiNode through an off-the-shelf SMT solver. The experimental results show that BiNode can reduce verification time by an order of magnitude through reducing/eliminating the cyclic dependencies among SMT variables.

Routing policy configuration plays a crucial role in determining the path that network traffic takes to reach a destination. Network administrators/operators typically decide the routing policy for their networks/routers independently. The paths/routes resulted from these independently configured routing policies might not necessarily meet the intent of the network administrators/operators. Even the very basic networkwide properties of the routing policies such as reachability between a pair of nodes need to be verified.In this paper, we propose a scheme that characterizes routingpolicy verification problems into a Satisfiability Modulo Theories (SMT) problems. The key idea is to formulate the SMT model in a policy-aware manner so as to reduce/eliminate the mutual dependencies between variables as much as possible. Further, we reduce the size of the generated SMT model through pruning. We implement and evaluate the policy-aware model through an outof-box SMT solver. The experimental results show that the policyaware model can reduce the time it takes to perform verification by as much as 100x even under a modest topology size. It takes only a few minutes to answer a query for a topology containing tens of thousands of nodes.

Network function virtualization (NFV) is a powerful networking approach that leverages computing resources to perform a time-varying set of network processing functions. Although microprocessors can be used for this purpose, their performance limitations and lack of specialization present implementation challenges. In this article, we describe a new heterogeneous hardware-software NFV platform called CoNFV that provides scalability and programmability while supporting significant hardware-level parallelism and reconfiguration. Our computing platform takes advantage of both field-programmable gate arrays (FPGAs) and microprocessors to implement numerous virtual network functions (VNF) that can be dynamically customized to specific network flow needs. The most distinctive feature of our system is the use of global network state to coordinate NFV operations. Traffic management and hardware reconfiguration functions are performed by a global coordinator that allows for the rapid sharing of network function states and continuous evaluation of network function needs. With the help of state sharing mechanism offered by the coordinator, customer-defined VNF instances can be easily migrated between heterogeneous middleboxes as the network environment changes. A resource allocation and scheduling algorithm dynamically assesses resource deployments as network flows and conditions are updated. We show that our deployment algorithm can successfully reallocate FPGA and microprocessor resources in a fraction of a second in response to changes in network flow capacity and network security threats including intrusion.

Over the past decade, a wide-ranging collection of network functions in middleboxes has been used to accommodate the needs of network users. Although the use of general-purpose processors has been shown to be feasible for this purpose, the serial nature of microprocessors limits network functional virtualization (NFV) performance. In this paper, we describe a new heterogeneous hardware-software approach to NFV construction that provides scalability and programmability, while supporting significant hardware-level parallelism and reconfiguration. Our computing platform uses both field-programmable gate arrays (FPGA) and microprocessors to implement numerous NFV operations that can be dynamically customized to specific network flow needs. As the number of required functions and their characteristics change, the hardware in the FPGA is automatically reconfigured to support the updated requirements. Traffic management and hardware reconfiguration functions are performed by a global coordinator which allows for the rapid sharing of middlebox state and continuous evaluation of network function needs. To evaluate our approach, a series of software tools and NFV modules have been implemented. Our system is shown to be scalable for collections of network functions exceeding one million shared states.

To enable billions of devices to communicate with each other simultaneously, small end-to-end latency and high scalability and reliability are the essential characteristics for the Internet of Things (IoT). The transition from today's Internet to IoT has demanded a new information and communications infrastructure. In this paper we implement and deploy a scalable and reliable inter-domain infrastructure, LORIF proposed in our previous work, to meet the requirements of IoT. Based on two local network testbeds and an intercontinental network testbed, we evaluate the scalability, resilience, and mobility of LORIF. The results demonstrate that LORIF can provide low end-to-end latency and high scalability and reliability.

A low-latency and reliable message switching network is critical for constructing high-speed datacenter networks. In this paper, we present the design, implementation, and evaluation of a novel Location basEd Source Switching (LESS) for datacenter networks. LESS enables lightweight source switching through a location-based addressing scheme. Each switch and host can independently derive a source route to reach a destination without requiring the full knowledge of the network topology. We demonstrate that using location-based source routes as forwarding labels allows LESS to eliminate the need for routing tables and integrate with minimum required functionality for packet forwarding. Moreover, we propose a fast rerouting solution to address the issue of fault tolerance in source routing. Each switch can locally derive an alternative source route during a failure. The paper evaluates the performance of LESS. Our evaluation results suggest that LESS improves the performance of datacenter networks in terms of latency, throughput, and reliability.

Network Functions (NFs) are deployed in networks for a variety of purposes, e.g. monitoring, security, or performance optimization. During packet processing, NF maintains the states of processed packets and/or manipulates packets based on these states. Some of these states are per-flow states while others are multi-flow states. With the emerging of network function virtualization (NFV), it is common to deploy an NF across multiple middleboxes for high processing capability. In this case, per-flow states can be maintained by each middlebox as its local states. The multi-flow states are global states that are shared among middleboxes. We propose a network function framework, Coordinator for Global States (CoGS), to scale a network function with global states across distributed middleboxes. A coordinator is adopted to manage global states for middleboxes. Meanwhile, each middlebox is able to access the states and process packets based on the global states. Our evaluation shows that the CoGS coordinator can handle more than 1 million state operations per second. With CoGS to manage the global states, the distributed NF achieves nearly linear scalability with a dozen of middleboxes.

As the Internet of Things technologies evolve, billions of smart devices will be connected to the Internet. Therefore, the accelerated growth of users, applications and devices pose a great demand on the scalability of the Internet. In this paper, we develop a new Internet architecture -- Multiple-inherited Locators (MiL) -- to meet the future demand on addressing. MiL is based on Locator/ID addressing and hierarchical address allocation. The benefit of this new addressing scheme is the improved scalability of Internet routing by enhancing the prefix aggregation of locators. The number of locators which are needed grows with the Internet scale. In order to represent each locator as a unique binary representation by as few bits as possible, we develop a distributed encoding method to efficiently encode locators. As the Internet topology evolves, the distributed encoding method renumbering locators' codeword for the optimal encoding performance, and meanwhile endeavors to keep their codewords unchanged as much as possible. Because, we want to represent locators by fewer bits as well as keep addressing stable. We adopt an Encoding Table Adjustment algorithm to find a "sweet spot" that balances these two goals. According to our experiment, within a 2% increase on the expected locator length, our algorithm reduces the cost of renumbering locator by 99.9%.

The Internet is facing the accelerating growth of routing table size. Backbone routers' routing table has already reached 512k entries, which has a negative effect on the scalability of the Internet. Hierarchical addressing and locator/ID separation solutions have been proposed to address the scalability issue. However, there has been little focus on how to efficiently represent hierarchical location addresses for a large scale distributed network, such as today's Internet. In this paper, we present a variable-length address encoding method to represent hierarchical location addresses. Our analysis and evaluation results show that 1) it is difficult to use fixed-length encoding to represent hierarchical location addresses for a large scale network; and 2) the proposed variable-length addresses could guarantee the scalability property of hierarchical addressing, and alleviate the inefficiency of address space due to fixed-length addresses.

Hierarchical address allocation and hierarchical routing design has long been suggested to reduce the forwarding information base (FIB) size in the Internet core. However, the hierarchical design is not put into practice. We implemented the hierarchical and automatic number allocation (HANA) protocol for allocation of IPv4 and IPv6 address spaces to autonomous systems (ASes) and the FIB size reduction. The HANA protocol allocates multiple address spaces to an AS from the upper ASes. Multihoming using multiple addresses provides an AS with multiple paths. That is, detour paths are inevitably prepared in advance, even when a network failure does not occur. In this paper, we provide the highest flexibility to HANA-based networking, namely, supporting variable-length addressing scheme. The variable-length addressing schemes suppress renumbering caused by the address space extension that occurs in the fixed-bit-length addressing schemes. In addition, we propose a new function of exchanging allocated numbers, and implement it in the current HANA system. The flexible HANA system provides locator allocation with low renumbering costs and realizes scalable addressing in future internetworking.

The Internet is facing the double-challenge of accelerating growth of routing table size and ever higher reliability requirements. Considerable progress has been made toward the scalability and reliability of the Internet. However, most of the proposals are only partial solutions that address some of the challenges. In this paper, we present a new addressing encoding scheme and a corresponding forwarding mechanism for Internet routing to solve the aforementioned problems. Underlying our design is a succinct data structure that allows us to compactly embed a set of addresses into packet headers. At the same time, the structure allows the data plane to efficiently extract multiple address information for the same destination without decompression. We provide time and space complexity analysis, and present experimental results evaluating the performance of our encoding method. It shows that the proposed encoding method can achieve a good compression factor without degrading packet-forwarding performance.

Runtime monitoring of Web service compositions has been widely acknowledged as a significant approach to understand and guarantee the quality of services. However, existing runtime monitoring solutions consider only the constraints on the sequence of messages exchanged between partner services and ignore the actual data contents inside the messages. As a result, it is difficult to monitor some dynamic properties such as how message data of interest is processed between different participants. To address this issue, we propose an efficient, non-intrusive online monitoring approach to dynamically analyze data-centric properties for service-oriented applications involving multiple participants. By introducing Par-BCL - a Parametric Behavior Constraint Language for web services - to define monitoring parameters, various data-centric temporal behavior properties for Web services can be specified and monitored. This approach broadens the monitored patterns to include not only message exchange orders, but also the data contents bound to the parameters. To reduce runtime overhead, we statically analyze the monitored properties to generate parameter state machine from the event pattern automata to optimize monitoring. The experiments show that our solution is efficient and promising.