The current IaaS model has several shortcomings. First, several IaaS providers only offers VM (virtual machine) with predefined sizes, thus enterprise tenants must judiciously determine the VM size that best fit their application. This is challenging as overprovisioning VMs can lead to waste of resources while underprovisioned VMs can lead to poor performance. Second, when an application requires more resources than a VM can provide, tenants are currently limited to either scaling-out or scaling-up their applications. However, in both situations the granularity is at the level of VMs which leads to sizing issues discussed earlier. Third, scaling-up is ineffective as it incurs a significant amount of downtime/poor performance while the new VM is being provisioned and not all applications support scaling-out. For example while, Web servers can be easily scaled-out other legacy applications can not [1], thus limiting its applicability.

Many cloud applications are data intensive requiring the processing of large data sets and the MapReduce/Hadoop architecture has become the de facto processing framework for these applications. Large data sets are stored in data nodes in the cloud which are typically SAN or NAS devices. Cloud applications process these data sets using a large number of application virtual machines (VMs), with the total completion time being an important performance metric. There are many factors that affect the total completion time of the processing task such as the load on the individual servers, the task scheduling mechanism, communication and data access bottlenecks, etc. One dominating factor that affects completion times for data intensive applications is the access latencies from processing nodes to data nodes. Ideally, one would like to keep all data access local to minimize access latency but this is often not possible due to the size of the data sets, capacity constraints in processing nodes which constrain VMs from being placed in their ideal location and so on. When it is not possible to keep all data access local, one would like to optimize the placement of VMs so that the impact of data access latencies on completion times is minimized. We address this problem of optimized VM placement - given the location of the data sets, we need to determine the locations for placing the VMs so as to minimize data access latencies while satisfying system constraints. We present optimal algorithms for determining the VM locations satisfying various constraints and with objectives that capture natural tradeoffs between minimizing latencies and incurring bandwidth costs. We also consider the problem of incorporating inter-VM latency constraints. In this case, the associated location problem is NP-hard with no effective approximation within a factor of 2 - ϵ for any ϵ > 0. We discuss an effective heuristic for this case and evaluate by simulation the impact of the various tradeoffs in the optimization objectives.

We consider resource allocation algorithms for distributed cloud systems, which deploy cloud-computing resources that are geographically distributed over a large number of locations in a wide-area network. This distribution of cloud-computing resources over many locations in the network may be done for several reasons, such as to locate resources closer to users, to reduce bandwidth costs, to increase availability, etc. To get the maximum benefit from a distributed cloud system, we need efficient algorithms for resource allocation which minimize communication costs and latency. In this paper, we develop efficient resource allocation algorithms for use in distributed clouds. Our contributions are as follows: Assuming that users specify their resource needs, such as the number of virtual machines needed for a large computational task, we develop an efficient 2-approximation algorithm for the optimal selection of data centers in the distributed cloud. Our objective is to minimize the maximum distance, or latency, between the selected data centers. Next, we consider use of a similar algorithm to select, within each data center, the racks and servers where the requested virtual machines for the task will be located. Since the network inside a data center is structured and typically a tree, we make use of this structure to develop an optimal algorithm for rack and server selection. Finally, we develop a heuristic for partitioning the requested resources for the task amongst the chosen data centers and racks. We use simulations to evaluate the performance of our algorithms over example distributed cloud systems and find that our algorithms provide significant gains over other simpler allocation algorithms.

Lack of well-defined defense perimeter in MANETs prevents the use traditional firewalls, and requires the security to be implemented in a distributed manner. We recently introduced a novel deny-by-default distributed security policy enforcement architecture for MANETs by harnessing and extending the concept of network capabilities. The deny-by-default principle allows compromised nodes to access only authorized services, limiting their ability to disrupt or even interfere with end-to-end connectivity and nodes beyond their local communication radius. The enforcement of policies is done hop-by-hop, in a distributed manner. In this paper, we present the implementation of this architecture, called DIPLOMA, on Linux. Our implementation works at the network layer, and does not require any changes to existing applications. We identify the bottlenecks of the original architecture and propose improvements, including a signature optimization, so that it works well in practice. We present the results of evaluating the architecture in a realistic MANET testbed Orbit. The results show that the architecture incurs minimal overhead in throughput, latency and jitter. We also show that the system protects network bandwidth and the end-hosts in the presence of attackers. To that end, we identify ways of creating multi-hop topologies in indoor environments so that a bad node cannot interfere with every other node. We also show that existing applications are not impacted by the new architecture, achieving good performance.

Self signed certificates for SSL and self generated hosts keys for SSH are popular zero cost, simple alternatives to public key infrastructure (PKI). They provide security against man in the middle attacks, as long as the the client connecting to those services knows the certificates or host keys a priori. A simple solution used in practice is to trust the certificate or the host key when the client connects to a server for the first time. This approach is susceptible to man in the middle attacks, a fact exploited by adversaries in a variety of attacks against unsuspecting users. We develop a simple and scalable solution named DoubleCheck to protect against such attacks. Our solution is achieved by retrieving the certificate from a remote host using multiple alternate paths. Our scheme does not require any new infrastructure; we make use of the Tor anonymity system to reach the destination using multiple independent paths. Hence our solution is easy to deploy in practice. Our solution does not introduce any privacy concerns. We have implemented DoubleCheck as SSH and Firefox extensions, demonstrating its practicality. Our experimental evaluation shows that the impact of DoubleCheck on performance is minimal, since the Tor network is used only for retrieving the certificate for the first time, while the data transfer and subsequent connection establishment follow normal routing rules. Our scheme is an effective way of mitigating the impact of man in the middle attacks without requiring new infrastructure and at low overhead.

Network QoS is essential for supporting real time interactive services such as VoIP. In the differentiated services framework QoS is provided by marking packets to receive preferential forwarding treatment, at each network node. This per hop forwarding treatment at each node may however be ineffective in providing the delay and jitter guarantees unless bounds are also imposed on the number of hops in the service routing paths. Interactive services also require minimal interruptions from network disruptions. Routing on hop limited paths may however have an adverse impact on the proportion of network capacity dedicated for protection to guarantee recovery from failures. In this paper we analyze this tradeoff in the context of MPLS fast reroute when protection capacities are pre-provisioned. We show that the underlying optimization problem is NP hard. We design almost best possible approximation algorithms for the problem and show that they work well in practice as well.

The phenomenal growth of the Internet in the last decade and society's increasing dependence on it has brought along, a flood of security attacks on the networking and computing infrastructure. Intrusion detection/prevention systems provide defenses against these attacks by monitoring headers and payload of packets flowing through the network. Multiple string matching that can compare hundreds of string patterns simultaneously is a critical component of these systems, and is a well-studied problem. Most of the string matching solutions today are based on the classic Aho-Corasick algorithm, which has an inherent limitation; they can process only one input character in one cycle. As memory speed is not growing at the same pace as network speed, this limitation has become a bottleneck in the current network, having speeds of tens of gigabits per second. In this paper, we propose a novel multiple string matching algorithm that can process multiple characters at a time thus achieving multi-gigabit rate search speeds. We also propose an architecture for an efficient implementation on TCAM-based hardware. We additionally propose novel optimizations by making use of the properties of TCAMs to significantly reduce the memory requirements of the proposed algorithm. We finally present extensive simulation results of network-based virus/worm detection using real signature databases to illustrate the effectiveness of the proposed scheme.

Multihop infrastructure wireless mesh networks offer increased reliability, coverage, and reduced equipment costs over their single-hop counterpart, wireless local area networks. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network, and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. Our evaluation demonstrates that our algorithm can effectively exploit the increased number of channels and radios, and it performs much better than the theoretical worst case bounds

The virtual concatenation protocol in SONET/SDH has ushered in a novel routing paradigm that enables a circuit to be "split" and routed over multiple paths. However, this diverse routing causes differential delay among the paths which can impact service if not accounted for in the routing. In this paper, we introduce the differential delay aware routing problem and show that it is not only NP-complete but is also provably hard to approximate within a constant factor. However, by transforming it into a flow routing formulation, we can derive effective, practical solutions. We present various algorithms and use extensive simulations to show that they are a good match to an "ideal" integer linear programming formulation. We also highlight how the differential delay data allows individual link delays to be reverse-engineered. We propose three algorithms to derive link delays including one that leverages the flexibility in the virtual concatenation protocol bits. Given the rise of next-generation applications such as online games where latency information is key, this knowledge of link delays, heretofore only loosely approximated, enables the telecom infrastructure to be more effective in supporting these applications.

Multi-hop infrastructure wireless mesh networks offer increased reliability, coverage and reduced equipment costs over their single-hop counterpart, wireless LANs. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. Our evaluation demonstrates that our algorithm can effectively exploit the increased number of channels and radios, and it performs much better than the theoretical worst case bounds.

Location tracking has several applications in mobile (cellular or ad hoc) networks, such as location-based routing algorithms and consumer services. It is often difficult to compute the location of a node precisely because of the infrastructure costs and the errors inherent in most tracking techniques. Furthermore, this accuracy differs amongst nodes based on the scattered availability of equipment such as GPS. We focus on heterogeneous mobile networks, wherein some nodes know their locations more precisely than others and there is a short-range peer-to-peer communication channel such as Bluetooth or 802.11. We consider a generalized notion of location, called vicinity, which is the set of potential locations for a node. We formulate a hierarchy of distance constraints that can be applied in a network and devise efficient distributed techniques for computing the most optimal (smallest) vicinities under various constraint classes. In particular, our algorithms use both proximity and non-proximity relationships between the nodes. We present simulation results establishing the effectiveness of using these different types of constraints.

Supporting fast restoration for general mesh topologies with minimal network over build is a technically challenging problem. Traditionally, ring based SONET networks have offered 50 ms restoration at the cost of requiring 100% over-build. Recently, fast (local) reroute has gained momentum in the context of MPLS networks. Fast reroute, when combined with preprovisioning of protection capacities and bypass tunnels, comes close to providing fast restoration for mesh networks. Preprovisioning has the additional advantage of greatly simplifying network routing and signaling. Thus even for protected connections, online routing can now be oblivious to the offered protection, and may only involve single shortest path computations. In this paper we are interested in the problem of reserving the least amount of the network capacity for protection, while guaranteeing fast restoration to all the supported connections. We show that the problem is NP-complete, and we present efficient approximation algorithms for the problem. These guarantees are provided even when the protection is for multiple link failures. In addition, the total amount of protection capacity reserved by these algorithms is just a small fraction of the amount reserved by existing ring-based schemes (e.g. SONET), especially on dense networks. The presented algorithms are computationally efficient, and can even be implemented on the network elements. Our simulation on some standard core networks, show that our algorithms work well in practice as well.

Network design tools are routinely used in practice to design optical networks that can carry a given set of traffic demands at the least cost The criteria used to route demands during design are often different from those used while routing in the operational network. As a result, the routes computed may be different during design and operations, leading to over- or under- utilization of portions of the network and even failure to route some demands. In this paper, we propose a general solution for this problem, which handles any combination of routing criteria. It works by enhancing the designed network with minimal additional capacity such that it can carry the demands during operations. We also provide experimental results evaluating the performance of this technique and the operational effectiveness of various design algorithms.

Fast shared restoration is critical to the success of WDM mesh networking. A restricted form of sharing called K-sharing was recently proposed, which allows rapid, signaling-free restoration. However, the routing and design algorithms used for traditional shared restoration do not work for this scheme. Also, K-sharing can potentially increase capacity requirements in the network because it limits sharing. In this paper, we present novel routing and design algorithms for K-shared networks. We also show that a practical version of the routing problem is NP-hard and present heuristics to solve it. We also summarize experimental results demonstrating that the additional capacity requirements imposed by K-sharing are in fact minimal in practice.