Overlay networking and ISP-assisted tunneling are effective solutions to overcome problematic BGP routes and bypass troublesome autonomous systems. Despite their demonstrated effectiveness, overlay support is not broadly available. In this paper, we propose Cloud-Routed Overlay Networks (CRONets), whereby users can readily build their own overlays using nodes from global and well-provisioned cloud providers like IBM Softlayer or Amazon EC2. While previous studies have demonstrated the benefits of overlay networks with the high-speed experimental Internet2 backbone, we are the first to evaluate the improvements in a realistic -- cloud -- setting. We conduct a large-scale experiment where we observe 6,600 Internet paths. The results show that CRONets improve the throughput for 78% of the default Internet paths with a median and average improvement factors of 1.67 and 3.27 times respectively, at a tenth of the cost of leasing private lines of comparable performance. We also performed a longitudinal measurement, and demonstrate that the performance gains are consistent over time with only a small number of overlay nodes needed to be deployed. However, given the size and dynamic nature of the Internet routing system (e.g., due to congestion and failures), selecting the proper path is still a challenging problem. To address it, we propose a novel solution based on the newly-introduced MPTCP extensions. Our experiments show that MPTCP can achieve the maximum observed throughput across the different overlay paths.

Today, the network design process remains ad hoc and largely complexity agnostic, often resulting in suboptimal networks characterized by excessive amounts of dependence and commands in device configurations. The unnecessary high configuration complexity can lead to a huge increase in both the amount of manual intervention required for managing the network and the likelihood of configuration errors, and thus must be avoided. In this paper, we present an integrated top-down design approach and show how it can minimize the unnecessary configuration complexity in realizing reachability-based access control, a key network design objective that involves designing three distinct network elements: virtual local-area network (VLAN), IP address, and packet filter. Capitalizing on newly developed abstractions, our approach integrates the design of these three elements into a unified framework by systematically modeling how the design of one element may impact the complexity of other elements. Our approach goes substantially beyond the current divide-and-conquer approach that designs each element in complete isolation, and enables minimizing the combined complexity of all elements. Specifically, two new optimization problems are formulated, and novel algorithms and heuristics are developed to solve the formulated problems. Evaluation on a large campus network shows that our approach can effectively reduce the packet filter complexity and VLAN trunking complexity by more than 85% and 70%, respectively, when compared with the ad hoc approach currently used by the operators.

The network design process today remains ad-hoc and largely complexity agnostic, often resulting in suboptimal networks characterized by excessive amounts of dependencies and commands in device configurations. The unnecessarily high configuration complexity can lead to a huge increase in both the amount of manual intervention required for managing the network and the likelihood of configuration errors, and thus must be avoided. In this paper we present an integrated top-down design approach and show how it can minimize the unnecessary configuration complexity in realizing user reachability control, a key network design objective that involves designing three distinct network elements: VLAN, IP address, and packet filter. Capitalizing on newly-developed abstractions, our approach integrates the design of the three elements into a unified framework by systematically modeling how the design of one element may impact the complexity of other elements. Our approach goes substantially beyond the current "divide-and-conquer" approach that designs each element in complete isolation, and enables minimizing the combined complexity of all elements. Specifically, two new optimization problems are formulated, and novel algorithms and heuristics are developed to solve the formulated problems. Evaluation on a large campus network shows that our approach can effectively reduce the packet filter complexity and VLAN trunking complexity by more than 85% and 70%, respectively, when compared to the ad-hoc approach currently used by the operators.

Enterprise networks often have complex routing designs given the need to meet a wide set of resiliency, security and routing policies. In this paper, we take the position that minimizing design complexity must be an explicit objective of routing design. We take a first step to this end by presenting a systematic approach for modeling and reasoning about complexity in enterprise routing design. We make three contributions. First, we present a framework for precisely defining objectives of routing design, and for reasoning about how a combination of routing design primitives (e.g. routing instances, static routes, and route filters etc.) will meet the objectives. Second, we show that it is feasible to quantitatively measure the complexity of a routing design by modeling individual routing design primitives, and leveraging configuration complexity metrics [5]. Our approach helps understand how individual design choices made by operators impact configuration complexity, and can enable quantifying design complexity in the absence of configuration files. Third, we validate our model and demonstrate its utility through a longitudinal analysis of the evolution of the routing design of a large campus network over the last three years. We show how our models can enable comparison of the complexity of multiple routing designs that meet the same objective, guide operators in making design choices that can lower complexity, and enable what-if analysis to assess the potential impact of a configuration change on routing design complexity.

Recent works, have shown the benefits of a systematic approach to designing enterprise networks. However, these works are limited to the design of greenfield (newly deployed) networks, or to incremental evolution of existing networks without altering prior design decisions. In this paper, we focus on redesigning existing networks, allowing for changes to existing decisions. Such redesign (migration) may be desirable from the perspective of improved network performance or lower complexity. However, the key challenge is that the costs of redesign may be high due to the presence of complex dependencies between network configurations. We consider these issues in the context of virtual local area networks (VLANs), an important area of enterprise network design. We make three contributions. First, we present a model to capture VLAN redesign costs. Such costs may arise from the need to reconfigure policies (e.g., security policies) to reflect the changes in VLAN design and ensure the continued correctness of the network. Second, we present a framework that enables operators to systematically determine the best strategies to redesign VLANs so the desired performance goals may be achieved while the costs of redesign are minimized. Finally, we demonstrate the effectiveness of our approach using data obtained from a large-scale campus network.

Enterprise networks are important, with size and complexity even surpassing carrier networks. Yet, the design of enterprise networks remains ad hoc and poorly understood. In this paper, we show how a systematic design approach can handle two key areas of enterprise design: virtual local area networks (VLANs) and reachability control. We focus on these tasks given their complexity, prevalence, and time-consuming nature. Our contributions are threefold. First, we show how these design tasks may be formulated in terms of network-wide performance, security, and resilience requirements. Our formulations capture the correctness and feasibility constraints on the design, and they model each task as one of optimizing desired criteria subject to the constraints. The optimization criteria may further be customized to meet operator-preferred design strategies. Second, we develop a set of algorithms to solve the problems that we formulate. Third, we demonstrate the feasibility and value of our systematic design approach through validation on a large-scale campus network with hundreds of routers and VLANs.

Enterprise networks are large and complex, and their designs must be frequently altered to adapt to changing organizational needs. The process of redesigning and reconfiguring enterprise networks is ad-hoc and error-prone, and configuration errors could cause serious issues such as network outages. In this paper, we take a step towards systematic evolution of network designs in the context of virtual local area networks (VLANs). We focus on VLANs given their importance and prevalence, the frequent need to change VLAN designs, and the time-consuming and error-prone process of making changes. We present algorithms for common design tasks encountered in evolving VLANs such as deciding which VLAN a new host must be assigned to. Our algorithms trade off multiple criteria such as broadcast traffic costs, and costs associated with maintaining spanning trees for each VLAN in the network, while honoring correctness and feasibility constraints on the design. Our algorithms also enable automatic detection of network-wide dependencies which must be factored when reconfiguring VLANs. We evaluate our algorithms on longitudinal snapshots of configuration files of a large-scale operational campus network obtained over a two year period. Our results show that our algorithms can produce significantly better designs than current practice, while avoiding errors and minimizing human work. Our unique data-sets also enable us to characterize VLAN related change activity in real networks, an important contribution in its own right.

In this paper, we tackle challenges in migrating enterprise services into hybrid cloud-based deployments, where enterprise operations are partly hosted on-premise and partly in the cloud. Such hybrid architectures enable enterprises to benefit from cloud-based architectures, while honoring application performance requirements, and privacy restrictions on what services may be migrated to the cloud. We make several contributions. First, we highlight the complexity inherent in enterprise applications today in terms of their multi-tiered nature, large number of application components, and interdependencies. Second, we have developed a model to explore the benefits of a hybrid migration approach. Our model takes into account enterprise-specific constraints, cost savings, and increased transaction delays and wide-area communication costs that may result from the migration. Evaluations based on real enterprise applications and Azure-based cloud deployments show the benefits of a hybrid migration approach, and the importance of planning which components to migrate. Third, we shed insight on security policies associated with enterprise applications in data centers. We articulate the importance of ensuring assurable reconfiguration of security policies as enterprise applications are migrated to the cloud. We present algorithms to achieve this goal, and demonstrate their efficacy on realistic migration scenarios.

Most prior work on the use of key management algorithms to enable confidentiality of video delivery has been conducted in the context of IP Multicast. In this paper, we consider the unique challenges and opportunities of integrating key management algorithms in an overlay multicast system. We conduct a systematic and extensive performance evaluation of strategies for key dissemination in the context of an operational overlay broadcasting system on the Planetlab testbed using real traces of join/leave dynamics. We show that leveraging TCP in each hop of the overlay dissemination structure can significantly simplify reliable key dissemination. The performance can be further enhanced if convergence properties of overlays are considered. We show that using two specialized dissemination structures, one for data and one for keys, potentially achieves low overhead for key dissemination without sacrificing application performance. To our knowledge, this is the first paper to study key management schemes in an overlay context using real implementation and Internet experiments and the first to consider issues in resilient key dissemination with overlays.

In this paper, we present an extensive study of key dissemination schemes in an overlay multicast context, and the first to involve actual implementation, real traces, and performance in Internet environments. Given that rekey traffic has stronger resilience requirements and is burstier than data traffic, we consider whether data and keys must be distributed using the same overlay or using two separate dissemination structures. Our key findings are: (i) a coupled architecture is effective in achieving resilient key dissemination. Using TCP in each hop of the dissemination structure (an opportunity unique to overlays) is effective in achieving resiliency in end-to-end key delivery. The performance can be further enhanced if convergence properties of overlays are considered; and (ii) a coupled architecture optimized for data delivery has high overheads, while a coupled architecture optimized for key delivery may not honor access bandwidth constraints of nodes. Distributing data and keys using separate overlays achieves low overhead for key dissemination while honoring access bandwidth constraints of nodes.