Search

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.

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.

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.

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.

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.

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

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.